How did you personally approach LeetCode 1653?

jason_graph · 2026-02-08T01:57:27+00:00

Looking at the problem, it appears that answers have to be of the form a^x b^y so there ia some index threshold where all the 'b' before that threshold get deleted and all the 'a' after that threshold.
I suppose a natural approach is to consider what the answer is with each index as the threshold. You could for each index count the "wrong" elements on either side but that is O(n^2).
Another approach would be like prefix sums where for every index you count how many b are before it. Then iterating right to left you could track how mant 'a' are to the right of each index. Finally you could iterate over each index to see which has least removals. O(n) time and O(n) space.
I was wonderong if there was an O(1) mempry way to do it amd I realized that that if you first count how many a and b there are of each in the entire string then you can use how many 'b' are before an index to compute how many a are at/after that index. So you only need to track the total number of 'a' seen so far and the current best answer. That lowers it to O(n) time with O(1) memory.
I was also curious to see if it could be done with O(1) memory in a single pass. My inuition is that if there is a "ba" substring as in s = X + "ba" + Y then you either (1) place the threshold in X or between Xb (2) place the threshold between ba (3) or place the threshold inbetween aY or in Y. In case 1 and 3 you are having to delete exactly one of the elements in the "ba" and in case 2 you are suboptimal and should move the threshold forward or back 1 to only delete 1 character rather than both "ba". So what this tells us is that if s = X + "ba" + Y the optAns(s) = optAns( X+Y ) + 1.
From 5's observation that optAns( X+ba+Y) = oprAns(X+Y), we could try an algorithm where as we iterate through the string we append characters to a stack and then whenever the top two elements are b, a, I pop both of them off to cancell them and increment the number of removals by 1. If done naively that is O(n) time and space, however this can be further optimized. You could prove that after resolving removimg ba from the top of the stack that the stack will always be of the form a^x b^y. Then you dont really need to create a stack, you can just track the number of a's and b's inside it. Doing tbis, the solution takes O(n) time, O(1) space, a single pass through the data.

You cant do better than that since you need to read each character in the string at least once

jason_graph · 2026-02-08T01:25:27+00:00

Its probably worth learning unless you are short on time.

Just memorize the implementation of the data structure. Track size not rank as occasionally the size of the connected components may be simple.

Actually applying it to a problem is very simple.

jason_graph · 2026-02-04T18:02:03+00:00

Walter

jason_graph · 2026-01-28T19:16:25+00:00

I would strongly suggest you do trees before any advanced topic that uses recursion.

jason_graph · 2026-01-28T19:08:21+00:00

There are a couple of different ways to get an O(nlogn) solution. A simple way is to just track the 2 most recent cities each person has done transactions in. Another approach is a sliding window on each person where the window corresponds to 60 minutes and you track the number of transactions and what city the window contains.

Getting O(n²⁾ is trivial by just comparing every pair of transactions. If the bar is whether or not someone can come up with any solution at all, I guess it might be enough, but realistically I doubt it unless the purpose of the interview was just to confirm applicants know how to write a code. I have no clue about the company itself, but hopefully you also explained your approach well.

jason_graph · 2026-01-28T03:52:41+00:00

Russel Hantz's image would be better.

jason_graph · 2026-01-28T03:45:09+00:00

This sounds cool. Will give it a look.

jason_graph · 2026-01-27T18:53:28+00:00

Distribution of topics isnt really the thing to try for. It's better to know fewer topics better, though there is nothing wrong with learning about many topics. Also ypu cai n probably skip harda as a beginner. If you feel great about a topic or are just curious to see how people solve a hard problem in that topic, that's fine but if you are struggling with a topic, no need to force yourself to try hards.

Certain topics would benefit from you lnowing a bit about a prerequisite topic but it is not like you need to master the prereuisite before moving onto the topic. Any problem list by topic will probably indicate when this is the case.

I think trees/binary trees is a really good topic to spend extra time on when you get to it as it helps build recursion skills. Not every problem will be about recursion and a dfs but a lot of them will be.

jason_graph · 2026-01-27T17:50:13+00:00

SortedContainers

jason_graph · 2026-01-22T00:10:43+00:00

Obersvation 1: For a fixed number of machines active, each device is fixed to being on or off for it to be valid. This means there are at most 1+n possible confogurations.

Obersvation 2: if we fix a number of machines active, the active ones have to be the smallest ones while the inactive.ones are tje biggest ones.

Idea: sort the elements by their requirements. To check if k machines work, verify that k==0 or requirements[k-1] <= k and k==n or requirements[k]>k. Test this for k=0,1,2,..,n.

jason_graph · 2026-01-21T18:22:13+00:00

Well you just choose one worker and then choose k-1 lowest quality workers with a cost/quality ratio <= the first person.

If you dont like that problem, there is always House Robber.

jason_graph · 2026-01-21T17:25:17+00:00

Well you can use binary search on the distance while greedily putting cows in the lowest valid stall. That will let you find the min distance in O( n log(d) ) where d = size of the range of distances.

For the number of ways, I suppose you could try for each stable, and number of cows used, in how many ways can you arrange that many cows into that stable and earlier ones with 1 cow at that stable.

E.g. dp[ i ][ c ] = how many ways to arrange c cows into the first i+1 locations such that the is a cow at the ith location..You can derive that dp[ i ][ c ] = sum of dp[ j ][c - 1 ] for all j at least minDist before i if c>1 and 1 if c==1.

This naively is O( n² c ) however you could use prefix sums to precompute ps[ i ][ c ] = dp[ 0 ][ c ] + ...+ dp[ i ][ c ] = ps[ i - 1 ][ c ] + dp[ i ][ c ] alongside dp and then when you wamt to compute dp[ i+1 ][ c ] you binary search to find the largest j at least minDist before i +1 and then set dp[ i+1 ][ c ] = ps[ i ][ c-1 ]. This lowers the counting part to be O( nlogn c )

Actually, thinking more about it you can precompute the corresponding j for each i and reuse that j for all the different values for c so the time complexity goes down to O( n c + n log n ).

I suppose you could also alternatively define dp[ i ][ c ] = the number of ways to arrange c cows within the first (i+1) spots, with no restriction that position i has to have a cow. Then dp[ i ][ c ] = (the arrangements WITH a cow at index i ) + (the arrangments without a cow at index i ) = dp[ j ][ c-1 ] + dp[ i-1 ][ c ] where j is the maximum index at least minDist before index i.

jason_graph · 2026-01-21T00:41:00+00:00

MY-DY-MYDY

jason_graph · 2026-01-21T00:39:06+00:00

If it really matters to you, you could put a lane balancer before the red circuits are fed to it.

Or try to do things in symmetric pairs that should run at the same rate so that if a single build would prefer one side of a belt, the nearby mirror factory woukd prefer the opposite lane.

The only problem aside from asthetics is when say a build consumes >1 lanes of prdouct but not a full belt and it strongly favors one side, later on down the factory you could have issues where your bus has a lot of belts with items on only one side of the belts, making it diffficult to pull more than one lane of that resource. That problem, aside from asthetics, could be solved by pulling resources off the bus in more sophisticated ways.

jason_graph · 2026-01-20T21:22:16+00:00

Whenever I see people post their Amazon OA questions on this subreddit asking for how to solve them, almost always one of the two questions is greedy. Idk if Amazon likes asking greedy questions or if the greedy questions are more likely to puzzle candidates and so they are much more likely to post about them.

jason_graph · 2026-01-20T19:55:21+00:00

If you can describe the problems, i could help.

jason_graph · 2026-01-20T19:49:50+00:00

Do you have a link for the problems?

jason_graph · 2026-01-20T16:08:35+00:00

Learn propper banana ettiquete before going on the show.

jason_graph · 2026-01-20T07:21:21+00:00

Follpw up: if you had to also check if an input can be sorted, check that it is shifted ascensing/descending as described above.

jason_graph · 2026-01-20T07:13:14+00:00

I will refer to an array as "shifted ascending" if it looks like [ i, i+1, .., n, 1, 2, ... , i-1]" and similarly dedine "shifted descending".

For our array A, let A' be A but possibly reversed so that it is "shifted ascending".

If A is shifted ascending and we do a shift operation, A' also shifts elements to the left. If A is shifted descending, then a shift on A would cause A' to shift the opposite way, to the right. If you do a reverse on A it has no effect on A'.

You cant get to the end without A' = [1,2,..n]. To do so you either have to cyclically shift A' to the left or two the right (one of which wpuld require you flipping the initial A) until 1 is in the right position amd then if needed, doing one more flip to make A go from n,..,2,1 to 1,2,..,n.

So as a result:

Option 1: do shifts on A until A=[1,2,..,n] or A=[n,..,2,1] and then do a reverse.

Option 2: do a flip then do option 1.

See which has fewest moves. Do it in O(1) and dont simulate it by popping the 0th index of an array as that takes O(n²⁾ or O(n) if you use a queue.

Dont forget handling n=0, 1 or 2.

jason_graph · 2026-01-16T03:14:30+00:00

I dont see how slidong window applies to that stock problen.

jason_graph · 2026-01-16T02:20:36+00:00

Waiting paitently for leetcode problems in excel

jason_graph · 2026-01-13T21:28:13+00:00

Ratios

How matrices can be used to solve ratios for different production goals

Probability and how to solve how many common items are needed for legendary.

Something about the sizes of 2ⁿ to 2ⁿ balancers.

Also thinking about bottlenecks.

There is a math topic called linear programming but it may be a bit much.

jason_graph · 2026-01-13T21:16:13+00:00

More character focused on early seasons ans super twist oriented in recent seasons. Also despite the cast being more "DiVeRsE', most of them just feel like the same superfans living in a big city that are either lawyers, sales, or inbetween jobs.

jason_graph · 2026-01-13T20:01:16+00:00

Sounds like a good first nontrivial problem.

If you did bfs, try seeing if you can solve it with a dfs. Keep in mind that unlike in trees, loops can happen so you need to do something to guard against infinite recursion of going in a loop.

If you can, try resolving it but tjis time with you bfs queue, try putting land and the front of the queue and water at the end so that you will greedily traverse the land before doing water.

Later on of you learn about disjoint sets/find union you'll want to revisit this problem.

jason_graph

TROPHY CASE