Skip to content
DevGod Repo
Blog

Blog

Leetcode 1970: Last Day Where You Can Still Cross

DevGod
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

DevGod
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

DevGod
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

DevGod
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.

Leetcode 55: Jump Game

DevGod
DevGod
Elf Vtuber

Question

In this Leetcode question, we are given an array of numbers. We start at the first index of the array, and our goal is to reach the end of the array. Each value of the array represents the maximum jump distance to the right. For example, if the first index’s value is 5, you could jump anywhere between 1 to 5 indexs ahead. If the index’s value is 0, then we are NOT allowed to jump anywhere beyond that spot, effectively trapping us. It is important to note that we are never given negative values in the given array. This means that leftward jumps are never allowed, given this constraint of the array Numbers.

Our goal is to determine if we can reach the end using any series of jumps. We return true or false depending on the reachability of the array’s end.

Solving

To solve this Leetcode problem, I used a greedy approach. I used a for loop to iterate left to right through the array. Whilst I traverse the array, the variable named maxJump records the furthest reachable index. In-between iterations, I check whether my current position is ‘impossible’ to reach. If an impossible index is detected, we return false and terminate early. If we go throughout the entire array, from left to right, without hitting an impossible to reach spot, we return true.

TLDR:

Used a Greedy approach to traverse the array, determining if the array’s end is reachable using any series of jumps. I solved this problem by iterating throughout the array, searching for impossible to reach spots.