Leetcode 1970: Last Day Where You Can Still Cross

Dec 29, 2025

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 26, 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)$$