Blog

Leetcode 3906: Count Good Integers on a Grid Path

Apr 23, 2026

Intuition

A “Good Integer” is simply an 16 digit integer whom has a non decreasing subsequence of integers at seven certain postions. The good integer itself doesnt have to be sorted, only the digits at those positions. Also the problem asks to find the total number of good integers within a given range.

The problem specifies that the 16 digit integer can be arranged into an imaginary four by four matrix, and that the given directions array controls how this matrix is traversed. This imaginary matrix traversal is what gives the directional path defined subsequence of visitied digits we want to check.

Digit DP, but with some extra logic to check previous digits at certain goal points. The problem boils down to finding out if certain positions depending on the given directions array can form a non decreasing subsequence of 7 digits. Starting from top left / most significant digit, and traversing as needed.

Biggest idea is dont actually try and create a 4 by 4 matrix for each integer possible in between the range, but rather use Digit DP to explore each possibility. Instead of moving down and right in a matrix, instead just jump forward in an array of digits either 1 or 4 depending on the given direction.

Approach

Create an array of digits with the given l and r numbers, whilst including enough leading zeros to to create an digit array of length 16. Then use digit DP to traverse possibiltiies between the given range, whom’s digits at certain positions follow the non decreasing pattern. For state, I use a seperate pos variable for tracking the current digit position, a dir variable for tracking which direction im evaluating, and a goal variable to check wether or not I reached the next position to check the previous digit of the path defined sequence.

Similar to other range summation problems, return both the amount of “Good Integers” possible from 0 to r, then subtract that by the possible count of 0 to l-1. Just like always, to avoid time limit errors, we use the power a memoization hashmap to protect our time.

TLDR

Digit DP to explore valid options recursively for a given range whilst simulating matrix traversal without actually creating a four by four matrix. Subtract the amounts found for left and right to get the total number of good integers.

Leetcode 1970: Last Day Where You Can Still Cross

Dec 30, 2025

DevGod

Elf Vtuber

About

The main idea was to check for a “Horizontal River” of connected water tiles that split the top and bottom land rows. I read the hints and saw that DFS with binary search for the days was also an option, but I really wanted to mix UnionFind with the horizontal river idea. It’s extremely messy but shockingly works for tonight.

Other notes that the river could consist of a completely horizontal line of water tiles, or include many diagonal cell connections. This is why unionFind is needed, and I can’t just check each row for a straight line of water tiles.

My first thought was to unionFind together all the starting land cells, then cut connections between them as water tiles are added. Instead, treating water tiles as unionFind connected components was a much easier thought process. Instead of having to constantly rerun DFS/BFS from top row cells to bottom row tiles, I could just check for this “horizontal river” of water tiles instead. Surprisingly, I didn’t even need to binary search through the “cells” coordinate array; I passed the LeetCode judge using only my UnionFind-based solution.

Solution

Uses Union find, with a custom method named floodCell. Also added a custom array this.flood for tracking the boolean status of whether a given cell is land or water. Also, instead of a traditional rank array for path compression/find optimization, I made this into a messy “unique column” tracking sets.

The thought is that if my number of unique columns for a connected water tile grouping is equal to the total number of columns in my pretend matrix, then I have formed a full-length horizontal river of water tiles.

The floodCell method sets this.flood with water/land status, updates “rank sets” with the new unique column values for the given connected water group, then, for the day’s event coordinates, checks around for fellow flooded neighbors.

If the neighbors are already flooded, then it unions them together and updates the neighbors’ unique column set ranking as well.

At the end, floodCell returns true if the act of watering the current day tile creates a full-length horizontal river bisecting the top and bottom row, otherwise returns false/

TLDR

Wasted so much time on UnionFind, this hard daily problem. Also wrote when sleepy, oof.

Leetcode 1351: Count Negative Numbers in a Sorted Matrix

Dec 27, 2025

DevGod

Elf Vtuber

About

For a given sorted matrix / grid with a mix of positive & negative integers, we have to return the amount of negative numbers present. Each column and row of the matrix is sorted in non increasing order. Being an easy problem with a small matrix grid size, we could go for a bruteforce nested forloop $$O(NM)$$ approuch. However, the solution can be more efficent using the power of binary searching each row, for a $$O(NlogM)$$ solution.

Solution

Given the small testcase constraints, we could use a bruteforce nested for loop to iterate through and count the total number of negatives. However, by preforming binary search on each row we can solve this problem more optimially tiem complexity wise.

I iterate throughout each row of the matrix, preforming a binary search to find the index of the first negative number in the row. Depending on where this first negative number index is, I subtract the total row length with it to grab the total number of negative numbers present in the row.

Due rows and columns of the matrix are sorted in non increasing order, I do another preformance boost by not setting $$R$$ varible back to $$R=grid[0].length-1$$. After completing the binary search on the current row, we can say that due to its sorted nature, the next row is guaranteed to have either the same or smaller $$R$$ index.

Lastly I keep a score varible as a running total of my negative numbers in the matrix grid. Once I am done iterating and binary searching each row, I return the score varible to solve the problem.

TLDR

Used binary search for each row to achieve a $$O(NLogM)$$ JavaScript solution.

Complexity

Time complexity: $$O(NLogM)$$
Space complexity: $$O(1)$$

Leetcode 2402: Meeting Rooms III

Dec 26, 2025

DevGod

Elf Vtuber

About

Given an integer n representing the total amount of rooms, and meetings including unique start times, and end times, find the room with the largest amount of held meetings & lowest room number.

If all n rooms are in use, we have to start delaying meetings. If a meeting is delayed, we still keep its original time duration consistant with its new delayed start time. For example, a meeting originally scheduled at [1,5] delayed two hours would be [3,7].

Unlike other meeting interval / range problems, this problem does not include the end time. This is known as half closed, which in other words means the next meeting can start at the same time as a meetings ending time.

Other big note is that in the event there are multiple unattended rooms, then the room with the smallest room number must be choosen. For example, if you are evaulating a meeting time, and rooms 1,2,3 are open, you MUST choose room 1.

Solution

Used a Priority Queue to track the order at which rooms will become available at given end times. Then sort the meetings by their unique start times, before iterating through each one. The roomScores array tracks the amount of times a room is used so I can find the room with the largest amount of meetings, and the smallest room number if multiple most meetings rooms exists.

We iterate through the sorted meetings, grabbing the start time and duration of each. Checks how many of the currently occupied rooms can be “marked as empty / available”, really this is just reassigning them to the rooms priority queue with the current meeting’s start time. This symbolizes / rearrenge which items are up next to use.

Push back into the rooms Priority queue with either the previous end time or the current meetings start time, then add the duration of the meeting. If we can start at the given start time great, else were gonna need to use prevTime and duration to simulate a delayed meeting due to all rooms being full.

Lastly, I just end the forloop interation by updating the roomScores frequency array with the total number of meetings at room numbers. Last if statements help keep track of the max and the room number answer to return.

Leetcode 58: Length Of Last Word

Jul 7, 2025

DevGod

Elf Vtuber

Question

In this Leetcode question, we are given a string representing a sentence. Each word is separated by the ” ” space character. Our goal is to return the length of the last word in the string. An important observation to note is that our given string could have white space characters before the start, as well as after the end. Additionally, more than one white space character could also separate each word in the string.

Solving

To solve this Leetcode problem, I start by using the built-in JS .trim() method. This trim method is able to remove all white space at the beginning and end of the string. By using trim on the given string, I can proceed with my JS methods knowing the end of the string is just the last word, and no additional space characters.

Next I use the string .split(” ”) method to split in-between space characters. This method transforms our trimmed string into an array of strings, separated by the space characters. As a side note, this method does leave some empty elements, but that is alright since the last element will just be our full last word. Since we are only concerned about the last element of this split array, any empty strings present in this string array can just be ignored. There is a way to use regular expressions to more accurately split the given string to avoid empty strings. However since I was more interested in code brevity, I instead used just a ” ” single space character instead.

After splitting our trimmed string into an array of strings, we can now pop() to return the last element. The pop method is a built-in JS array method, that removes and returns the last word of the split string array. Another way to retrieve the last element would have been with [s.trim().split(” “).length - 1]. While this is the slightly more time efficient way, the .pop() method just took less characters. Given the small constraints regarding the given string’s length, I preferred the least amount of code vs the most time efficient code.

Lastly, now that we have trimmed the original string, split it into an array of strings and popped the last element, we can now just return the .length property to answer the question.

TLDR:

I used built-in Javascript array and string methods to return the length of the last word in the given string.