Skip to content
DevGod Repo
Blog

Hard

2 posts with the tag “Hard”

Leetcode 3906: Count Good Integers on a Grid Path

DevGod
DevGod
Elf Vtuber

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

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.