Algos Prep

Nothing out of the ordinary here, there’s no indication of needing to handle integer overflow cases or to do any type changes.

Since it’s a member duplicates check and they’re only looking for bool output, can just resort to anything that is a default stdlib function.

Size checks make sense and the only problem I can fault this for is that it requires a duplication in memory because of the creation of the set.

The size checks via len should be fast because it’s a struct-value check.

1. I should spend a little bit longer trying to entertain the edge cases if it’s an in-person thing and someone is evaluating me for my thought process. If it’s a bot, then it’s alright I can just send as I wish.
2. It doesn’t have an early-exit pattern

• didn’t spend much time looking into this

1: from collections import Counter
2: 
3: class Solution:
4: │   def isAnagram(self, s: str, t: str) -> bool:
5: │   │   if (len(s) != len(t)):
6: │   │   │   return False
7: │   │   │
8: │   │   return Counter(s) == Counter(t)

• the length check is an early return that makes things fast

1. Character counting works great if we use collections::Counter which gives a refmap of the characters and their counts
2. The choice of DS is whether the charspace is fixed or not
3. Counter works with a hashtable under the hood.

• Question: will Counter() handle different encodings well?

  Answer: Yes: Counter works with any hashable object, including Unicode characters, so it will count any character in the input string, regardless of encoding

  Caveat: If you want to support Unicode, your code doesn’t need to change, but using a fixed-size array for counting would not work; you must use a hash table (Counter or dict).

• Other things that Counter can be used for

• in the realm of character counting there are other approaches that might make sense:
  • if the charset is known then can use a fixed array representing the charset might make sense. than can just count based on that fixed idx Datastructures for character counting:
  • Using a fixed-size array for counting is the most space-efficient for lowercase English letters, as it avoids hash table overhead and is always O(1) space
  • Sorting both strings and comparing them is another common approach, but it is O(nlog⁡n)O(nlogn) and thus less efficient than counting.

For efficiently counting character frequencies, several data structures can be considered, each with its own advantages:

1. **Hash Table (Dictionary in Python)**:
│  - **Time Complexity**: O(n) for counting frequencies, where n is the number of characters.
│  - **Space Complexity**: O(k), where k is the number of distinct characters.
│  - **Use Case**: Ideal for counting frequencies of characters or words, as it allows for constant-time complexity for insertions and lookups. This is especially useful for large datasets where you need to maintain a count of each unique character or word[2][4].
│
2. **Counter from `collections` Module**:
│  - **Time Complexity**: O(n).
│  - **Space Complexity**: O(k).
│  - **Use Case**: A specialized dictionary for counting hashable objects. It provides a clean and efficient way to count frequencies and is highly optimized for this purpose. It simplifies the code and is recommended for most frequency counting tasks in Python[6].
│
3. **List (for Fixed-Size Character Sets)**:
│  - **Time Complexity**: O(n).
│  - **Space Complexity**: O(1) if the character set size is fixed (e.g., ASCII or lowercase English letters).
│  - **Use Case**: Suitable for counting frequencies of characters when the character set is limited and known in advance. This approach uses a fixed-size list indexed by character codes, making it very efficient in terms of both time and space[2].
│
4. **Counting Sort**:
│  - **Time Complexity**: O(n + k), where k is the range of the input.
│  - **Space Complexity**: O(k).
│  - **Use Case**: Useful when you need to sort data based on frequency counts. It is efficient for small ranges of input values and when sorting is required based on frequency[7].
│
### Summary

For most general-purpose applications, using a `Counter` from Python's `collections` module is recommended due to its simplicity and efficiency. If you are dealing with a fixed character set, using a list to count frequencies can be slightly more efficient. For scenarios involving sorting based on frequency, counting sort can be a good choice.

Citations:
[1] https://stackoverflow.com/questions/74344201/appropriate-data-structure-for-counting-frequency-of-string
[2] https://www.geeksforgeeks.org/counting-frequencies-of-array-elements/
[3] https://discourse.julialang.org/t/how-to-count-all-unique-character-frequency-in-a-string/19342
[4] https://users.rust-lang.org/t/efficient-string-hashmaps-for-a-frequency-count/7752
[5] https://www.sololearn.com/en/Discuss/2705816/letter-frequency-on-python-data-structures
[6] https://towardsdatascience.com/3-ways-to-count-the-item-frequencies-in-a-python-list-89975f118899?gi=dcc78c14cf09
[7] https://www.geeksforgeeks.org/counting-sort/
[8] https://docs.python.org/uk/3/tutorial/datastructures.html

No specific time constraint given, good if less than O(n²).

 1: from collections import defaultdict
 2: 
 3: class Solution:
 4: │   def twoSum(self, nums: List[int], target: int) -> List[int]:
 5: │   │   # refmap: indices itself
 6: │   │   refmap = defaultdict(bool)
 7: │   │   for idx, num in enumerate(nums):
 8: │   │   │   complement = target - num
 9: │   │   │   if (complement in refmap):
10: │   │   │   │   return [idx, refmap[complement]]
11: │   │   │   else:
12: │   │   │   │   refmap[num] = idx
13: │   │   │   │
14: │   │   # no fallthrough, ans is guaranteed

So Kinda did a small oopsie, the defaultdict not really necessary, we could have just used a dict.

Even clearer solution:

1: class Solution:
2: │   def twoSum(self, nums: List[int], target: int) -> List[int]:
3: │   │   num_to_index = {}
4: │   │   for idx, num in enumerate(nums):
5: │   │   │   complement = target - num
6: │   │   │   if complement in num_to_index:
7: │   │   │   │   return [num_to_index[complement], idx]
8: │   │   │   num_to_index[num] = idx

• Time Complexity:
  • Each lookup and insertion in the dictionary is \(O(1)\) on average.
  • You traverse the list once: \(O(n)\) time.
• Space Complexity:
  • In the worst case, you store every number in the dictionary: \(O(n)\) space.

Classic question.

This time I ensured to use collections::defaultdict to make things easy. No new discoveries as I did this yet.

This should be the most efficient in terms of space (since we return early as we build a dict) and time. It should be faster than \(O(n^2)\) because we only do a single pass and make reference to a visited collection. So runtime and space should be linear here.

The refmap can be better named to include information of what is held, although that feels more like a nitpick.

• nothing out of the ordinary for this, just had to make sure the empty string was handled well.

1. I treated it as a counting task yet again but in this case I realise that the overuse of stdlib functionality can be costly. So my initial solution was too slow compared to the population and I had to try make it better.

1. Anagram checks can be derived based on thinking about what they are. Anagrams ==> permutations of the same collection of characters ==> sorting can make two anagrams equal ==> we can use this to do checks
2. Time complexities.

   • my improved solution : Time Complexity: For each string of length k, you count letters in O(k). For n strings, total time is O(N*K), where N = number of strings, K = average string length.

     Space Complexity: O(N*K) for storing all strings and their groupings. O(N) for the dictionary keys (one per unique anagram group).

1. Couldn’t find anything extraordinary for this
2. Runtime must be better than O(n logn)

Counter based solution:

1: from collections import Counter
2: 
3: class Solution:
4: │   def topKFrequent(self, nums: List[int], k: int) -> List[int]:
5: │   │   return [elem for [ elem, _ ] in Counter(nums).most_common(k)]

• Time: Counter(nums) is O(n). most_common(k) is O(n log k) if implemented with a heap, but in CPython, it actually sorts, so it’s O(n log n).
• Space: O(n) for the frequency map.

1. Just adopted another counting approach since the counter has the ability to do most_common.
2. Went for the first-reach, the non-lib approach would probably be similar, just with manual code for the counting part

1. Bucket sort works perfectly for the frequency comparisons. The key problem via other methods is that we shouldn’t be sorting the individual frequencies like that Here’s the intuition behind things:

   Show/Hide Md Code

   Here’s an intuitive breakdown of **why bucket sort or a heap is better** than a full sort for the Top K Frequent Elements problem, and how you can arrive at these solutions:
   
   ## **Why Not Full Sort?**
   A naive approach is to:
   - Count frequencies (O(n))
   - Sort all items by frequency (O(n log n))
   - Take the top k
   
   But the problem asks for better than O(n log n) time.
   
   ## **Bucket Sort Intuition**
   
   ### **Key Insight**
   - **Frequencies are integers between 1 and n** (where n is the array length).
   - You don’t care about the exact order—just the k most frequent elements.
   
   ### **How Bucket Sort Works Here**
   1. **Count frequencies** of each element (O(n)).
   2. **Create buckets**:
   │  - Make an array of n+1 lists (buckets), where index i holds all elements that appear i times.
   3. **Fill the buckets**:
   │  - For each number and its frequency, put it in the bucket at index = frequency.
   4. **Collect results**:
   │  - Starting from the highest-frequency bucket, collect elements until you have k.
   │
   ### **Why is this O(n)?**
   - Counting is O(n).
   - Filling buckets is O(n).
   - Collecting top k is O(n) (since at most n unique elements).
   - **No sorting needed!**
   │ This leverages the fact that the range of possible frequencies is small and bounded by n[3][4][6][7].
   │
   ## **Heap Intuition**
   
   ### **Key Insight**
   - You want the k largest frequencies, not a full sort.
   
   ### **How Heap Works Here**
   1. **Count frequencies** of each element (O(n)).
   2. **Use a min-heap of size k**:
   │  - For each unique element, push (frequency, element) into the heap.
   │  - If heap size exceeds k, pop the smallest.
   3. **At the end, the heap contains the k most frequent elements**.
   
   ### **Why is this O(n log k)?**
   - Each insertion/popping from the heap is O(log k).
   - For n unique elements, total time is O(n log k).
   - Much better than O(n log n) if k is small compared to n[2][4][5][8].
   
   ## **How to Arrive at These Solutions**
   
   ### **Bucket Sort:**
   - After counting, realize that the number of possible frequencies is at most n.
   - Instead of sorting, group elements by frequency directly.
   - This is a classic bucket sort scenario: small, dense range of keys (frequencies).
   
   ### **Heap:**
   - If you only need the k largest, a heap naturally supports this.
   - Using a min-heap of size k ensures you always keep the k most frequent seen so far.
   - This is a standard approach for "top k" problems.
   
   ## **Summary Table**
   
   | Approach      | Time Complexity | When to Use                         | Intuition                       |
   |---------------|----------------|-------------------------------------|---------------------------------|
   | Full Sort     | O(n log n)     | Not optimal for large n             | Sort everything                 |
   | Bucket Sort   | O(n)           | When range of keys (freq) is small  | Group by freq, no sorting needed|
   | Heap (min-k)  | O(n log k)     | When k is much smaller than n       | Only keep k largest             |
   
   ### **References to Search Results**
   - Bucket sort leverages the bounded nature of frequencies for O(n) grouping[3][4][6][7].
   - Heap approach is efficient for top-k selection, avoiding full sort[2][5][8].
   
   If you want a more detailed code walk-through or further intuition, let me know!
   
   [1] https://www.geeksforgeeks.org/find-k-numbers-occurrences-given-array/feed/atom/
   [2] https://www.youtube.com/watch?v=YPTqKIgVk-k
   [3] https://cs.stackexchange.com/questions/168505/top-k-most-frequent-elements-and-bucket-sorting-intuition
   [4] https://neetcode.io/solutions/top-k-frequent-elements
   [5] https://www.cnblogs.com/hygeia/p/5759512.html
   [6] https://leetcode.com/problems/top-k-frequent-elements/discuss/81602/Java-O(n)-Solution-Bucket-Sort
   [7] https://www.byteinthesky.com/tutorials/top-k-frequent-elements/
   [8] https://stackoverflow.com/questions/67073941/top-k-frequent-elements-time-complexity-bucket-sort-vs-heap
   [9] https://algo.monster/liteproblems/347
   [10] https://www.youtube.com/watch?v=SY26k8ZswPY
   

2. Question: the constraint of “time complexity must be better than O(n logn)” – what is it supposed to hint? Answer:Hint:
   • You should avoid sorting all elements.
   • Use a heap (O(n log k)) or bucket sort (O(n)) for optimal performance.
3. Question: could I have used a accessor function when using the sorted function to determine what to sort by? Answer: yes, the key parameter accepts a lambda function

• No integer overflows expected, min speed should be O(n).
  • the number of passes don’t matter
• Stretch: Use O(1) space only
  • we have to use the output array itself.

It was clear that the O(n) suggests that we should try a sweeping approach, do a prefix/suffix partial products and then calculate them together.

The O(1) space consideration was oddly phrased but the rough idea is that we can use the same output array that we intended to use for the result and in so doing we can keep it as O(1).

Intermediate results can be just kept in the array itself and a temporary variable can be used for the lookbacks or lookaheads.

1. I think I analysed this well, the intuition was there from the first time that I had done this.
2. The reverse step needs to be understood for better intuition so reversed should be range(n - 1, -1, -1) where the start is inclusive index n - 1, the end is exclusive index -1 (so that 0 is counted) and the step is reversed -1.
3. Question: what can be faster than this? Answer: nothing. I’m blazingly fast already Nothing can be faster than O(n) for this problem, since you must look at every element at least once. The only possible “faster” would be reducing constant factors, but your code is already optimal in both time and space. Any approach using division (with special handling for zeros) is not allowed per the problem.

1. only some rules given, just have to evaluate ONLY them
2. no need to care about empty slots
3. just need to do repetition check

My solution just runs the 3 rules separately. If there are more rules, then each rule evaluation can be function-pointered and we could just add them as we wish. The code for the frequency check is the same regardless of slice.

Also this time I didn’t have much of a problem defining the slices because I have a better intuition for why the ranges are defined like they are.

 1: class Solution:
 2: │   def isValidSudoku(self, board: List[List[str]]) -> bool:
 3: │   │   # handle the rows:
 4: │   │   for row in board:
 5: │   │   │   frequency_ref = [0] * 9 # index = ord edit distance
 6: │   │   │   for val in row:
 7: │   │   │   │   if (val == '.'):
 8: │   │   │   │   │   continue
 9: │   │   │   │   idx = ord(val) - ord('1')
10: │   │   │   │   has_duplicate = frequency_ref[idx] > 0
11: │   │   │   │   if (has_duplicate):
12: │   │   │   │   │   return False
13: │   │   │   │   frequency_ref[idx] += 1
14: │   │   │   │
15: │   │   # handle the columns:
16: │   │   for col_idx in range(0, 9):
17: │   │   │   frequency_ref = [0] * 9 # index = ord edit distance
18: │   │   │   column = (row[col_idx] for row in board)
19: │   │   │   for val in column:
20: │   │   │   │   if (val == '.'):
21: │   │   │   │   │   continue
22: │   │   │   │   idx = ord(val) - ord('1')
23: │   │   │   │   has_duplicate = frequency_ref[idx] > 0
24: │   │   │   │   if (has_duplicate):
25: │   │   │   │   │   return False
26: │   │   │   │   frequency_ref[idx] += 1
27: │   │   │   │
28: │   │   # handle sub_boxes:
29: │   │   top_left_corners = ((row_idx_start, col_idx_start) for col_idx_start in range(0, 9, 3) for row_idx_start in range(0, 9, 3))
30: │   │
31: │   │   for row_start, col_start in top_left_corners:
32: │   │   │   frequency_ref = [0] * 9 # index = ord edit distance
33: │   │   │   for val in (board[row_idx][col_idx] for row_idx in range(row_start, row_start + 3) for col_idx in range(col_start, col_start + 3)):
34: │   │   │   │   if (val == '.'):
35: │   │   │   │   │   continue
36: │   │   │   │   idx = ord(val) - ord('1')
37: │   │   │   │   has_duplicate = frequency_ref[idx] > 0
38: │   │   │   │   if (has_duplicate):
39: │   │   │   │   │   return False
40: │   │   │   │   frequency_ref[idx] += 1
41: │   │   │   │
42: │   │   return True

1. for the repetition check part, it’s clear that the fixed char space for 1 to 9 digits means that we can do a very efficient way of doing fixed-array frequency checks. Just use ord(val) - ord(-1) to get the edit distance, which becomes the index in the array. The bot praised me “Your use of ord(val) - ord(‘1’) is clever for fixed-size arrays.”
2. I acknowledge that my approach has 3 readings per cell and this is technically wasteful
3. the rest of it is a matter of being able to define python slices correctly.

1. the edit distance as a way of judging the index within the fixed sized frequency ref-array is pretty neat!
2. The single-pass approach is better for n-dimensional. In this case, it’s tolerable because the board-size is fixed.

3. Question: One of the better solutions online looks like this but I don’t have an under-the-hood understanding of why that is significantly faster (other than avoiding the duplicate reads for each cell)

   Show/Hide Python Code

    1: class Solution:
    2: │   def isValidSudoku(self, board: List[List[str]]) -> bool:
    3: │   │   cols=defaultdict(set)
    4: │   │   rows=defaultdict(set)
    5: │   │   squares=defaultdict(set)
    6: │   │   for r in range(9):
    7: │   │   │   for c in range(9):
    8: │   │   │   │   if board[r][c]==".":
    9: │   │   │   │   │   continue
   10: │   │   │   │   if (board[r][c] in rows[r] or board[r][c] in cols[c] or board[r][c] in squares[(r//3,c//3)]):
   11: │   │   │   │   │   return False
   12: │   │   │   │   cols[c].add(board[r][c])
   13: │   │   │   │   rows[r].add(board[r][c])
   14: │   │   │   │   squares[(r//3,c//3)].add(board[r][c])
   15: │   │   return True
   

• it must run in O(n) time, so no direct sorting or anything
  • however, does this mean that we can sort groups as we accumulate groups? ANS: NO such thing
• initial array is unsorted

Initial failed attempt:

• My approach was to define ranges/intervals using tuples. iterate through the nums and each time there are 3 cases:
  1. The num is within an existing range
  2. the num is to the left extending of an existing range ==> we can replace the tuple with an updated range
  3. the num is to the right extending of an existing range ==> we can replace the tuple with an updated range Once I’ve tried to group up all the numbers, then I just need to check if any of the existing ranges can be merged with each other to create bigger super ranges. Like a cascade of sorts. however, I don’t know how to do this cascade of sorts

Final Insight:

1. it’s really just a noop sled like that: The key insight is: You only need to start climbing from the “base” of a ladder (the minimal element of a sequence)—if you start anywhere else, you’re not at the true start, and you’ll be duplicating work.

1. Problems with original solution:
   1. it introduces the problem of needing to merge intervals and interval-merging intervals efficiently should be seen as a hard problem
   2. the inner loop run makes the overall thing O(n²) which violates the requirement that we are given that it needs to be done in O(n) time.
2. Interval merging efficiently should be seen as a hard problem to solve
3. Key Intuition: The key insight is: You only need to start climbing from the “base” of a ladder (the minimal element of a sequence)—if you start anywhere else, you’re not at the true start, and you’ll be duplicating work.
   1. We can use a set for O(1) lookups, we just need to find the start of each sequence to see if num - 1 is NOT in the set
   2. for each “start” we can count upwards until we no longer find consecutive numbers
4. More intuition aspects: When you see “longest consecutive sequence” and an O(n) requirement, think:
   • Can I use a set for O(1) lookups?
   • Can I only start counting at the minimal element of a sequence? Avoid interval merging unless the problem is specifically about merging sorted intervals.

5. Extensions, more on interval merging:

   Show/Hide Md Code

   The **most efficient and standard way to merge intervals** is as follows:
   
   ### **1. Sort the intervals by their start time**
   
   Sorting ensures that any overlapping intervals are adjacent, so you only need to compare each interval to the last merged one[1][2][3][5][6][7][9].
   
   ### **2. Iterate and merge**
   
   - Initialize a result list with the first interval.
   - For each subsequent interval:
   │   - If it overlaps with the last interval in the result (i.e., its start is less than or equal to the end of the last merged interval), merge them by updating the end of the last interval to the maximum of both ends.
   │   - If it does not overlap, simply append it to the result list.
   │
   ### **3. Time Complexity**
   
   - **Sorting:** O(n log n)
   - **Merging:** O(n)
   - **Total:** O(n log n) (dominated by the sorting step)[3][5][6][7].
   
   #### **Python Example**
   
   ```python
   def merge(intervals):
   │   if not intervals:
   │   │   return []
   │   # Step 1: Sort intervals by start time
   │   intervals.sort(key=lambda x: x[0])
   │   merged = [intervals[0]]
   │   # Step 2: Iterate and merge
   │   for current in intervals[1:]:
   │   │   last = merged[-1]
   │   │   if current[0] <= last[1]:
   │   │   │   # Overlap: merge
   │   │   │   last[1] = max(last[1], current[1])
   │   │   else:
   │   │   │   # No overlap: add new interval
   │   │   │   merged.append(current)
   │   return merged
   ```
   
   ### **Why Not O(n)?**
   
   - The need to sort the intervals by start time is fundamental for efficient merging; without sorting, you’d need to check all pairs, which is O(n²)[3][5].
   - There are advanced data structures (like interval trees or balanced BSTs) that can support dynamic merging in streaming scenarios, but for the classic merge-intervals problem, **O(n log n)** via sorting is optimal and standard[10].
   
   ### **Summary Table**
   
   | Approach           | Time Complexity | When to Use                                  |
   |--------------------|----------------|----------------------------------------------|
   | Sort + Merge (std) | O(n log n)     | Most general and efficient for static input  |
   | Naive (nested)     | O(n²)          | Only for very small input or educational use |
   | Interval Tree      | O(n log n)     | For dynamic/streaming intervals              |
   
   **In short:**
   **Sort by start time, then merge adjacent intervals in a single pass. This is the most efficient and standard approach for merging intervals.**[1][2][3][5][6]
   
   If you need to handle intervals in a streaming fashion (i.e., intervals arrive one at a time), an interval tree or balanced BST can be used for efficient dynamic merging, but that’s a more advanced scenario[10].
   
   [1] https://algocademy.com/blog/merge-intervals-a-comprehensive-guide-to-solving-this-classic-algorithm-problem/
   [2] https://www.architectalgos.com/mastering-merge-interval-patterns-a-guide-to-solving-interval-based-problems-1a14ef065876
   [3] https://www.geeksforgeeks.org/dsa/merging-intervals/
   [4] https://leetcode.com/problems/merge-intervals/
   [5] https://www.educative.io/interview-prep/coding/solution-merge-intervals
   [6] https://algocademy.com/blog/mastering-merge-interval-problems-essential-techniques-for-coding-interviews/
   [7] https://docs.vultr.com/problem-set/merge-intervals
   [8] https://www.w3resource.com/data-structures-and-algorithms/array/dsa-merge-intervals.php
   [9] https://blog.seancoughlin.me/mastering-the-merging-of-overlapping-intervals-in-python
   [10] https://stackoverflow.com/questions/4748184/how-to-efficiently-merge-int-ranges-in-a-stream
   

1. there’s negative numbers so this means that the same prefix sum value may appear more than once

1. this is a subarray sum. Classical question for prefix-sum approaches.

1. prefix sum approaches to solving range sum type questions.
2. careful:
   1. single pass, order of filling the prefix sum table matters
   2. remember the trivial helper values (e.g. prefix_count[0] = 1)
3. sliding window would ONLY have worked here if we had NO non-negative values
4. the v1 solution can be interpreted as a DP solution as well:
   • Dynamic Programming?
     • Yes — we store the counts of prefix sums (that’s memoization of subproblems).
     • Optimal substructure: The count of valid subarrays ending at index i depends on best solutions to subproblems ending earlier (j < i).
     • Overlapping subproblems: many subarrays share the same prefix sums, so we reuse them via hashmap.
     • So your v1 approach is really prefix-sum DP disguised as hashing.

Nothing fancy, the inputs imply that it has to be in linear time.

My solution just uses python language features (counters, enumeration, generators) and makes the performance alright, nothing fancy here.

1. first time I used generators like that.

<e.g., “I struggled with X”, “I want to know about alternative algorithms”, etc.>

1. Case insensitive
2. we need to ignore non alnum: alnum check can be done in python using "mystring".isalnum() or 'a'.isalnum() and that’s really convenient.
3. main edge case that slowed me down: “empty string” conditions. In the case of the moving pointer, it means that the left and right pointers are at the end and beginning of the list respectively.

1. Ignoring other pythonic stdlib solutions, or using any other aux data structure here because the input constraint can be big.
2. It’s a converging 2 pointer solution, we just do until they overrun. At each iteration, either pointer may shift more than once – kinda greedy.

1. there’s definitely a solution, so no fallthrough necessary
2. It’s 1-indexed. This shouldn’t throw anyone off-guard, should be seen as just a answer-formatting requirement, instead of anything that affects the actual logic of things.

 1: class Solution:
 2: │   def twoSum(self, numbers: List[int], target: int) -> List[int]:
 3: │   │   left, right = 0, len(numbers) - 1
 4: │   │   while left < right:
 5: │   │   │   current_sum = numbers[left] + numbers[right]
 6: │   │   │   if current_sum == target:
 7: │   │   │   │   return [left + 1, right + 1]
 8: │   │   │   │
 9: │   │   │   if current_sum < target:
10: │   │   │   │   left += 1
11: │   │   │   │   continue
12: │   │   │   │
13: │   │   │   if current_sum > target:
14: │   │   │   │   right -= 1
15: │   │   │   │   continue
16: │   │   │   │
17: │   │   # no fallthrough needed, exactly one solution guaranteed

This is the optimal solution:

• time complexity: O(n) because each pointer moves at most n times
• Space: O(1) time, all in-place just some helper const variables used

A slightly clearer way to write this, without the continue statements will look like this:

 1: class Solution:
 2: │   def twoSum(self, numbers: List[int], target: int) -> List[int]:
 3: │   │   left, right = 0, len(numbers) - 1
 4: │   │   while left < right:
 5: │   │   │   current_sum = numbers[left] + numbers[right]
 6: │   │   │   if current_sum == target:
 7: │   │   │   │   return [left + 1, right + 1]
 8: │   │   │   elif current_sum < target:
 9: │   │   │   │   left += 1
10: │   │   │   else:
11: │   │   │   │   right -= 1

The if-elif-else handles the control flow for us more easily.

1. the key intuition from me here is that at any iteration, we only move one of the pointers. Since there’s a monotonically increasing order, it would mean that we either need to shift left pointer (to make the sum bigger) or shift the right pointer (to make the sum smaller).
2. if pointers overrun, there’s no answer because the search space would have been exhausted by that point.

1. I keep missing the -1 for the right pointer initialisation to be len(s) - 1

• we need to return actual values, not the indices here
• runtime expected is roughly going to be \(O(n^2)\) because it scales in the order of magnitude from 2-sum
• 2 pointer method will likely be faster than extra aux datastructures use because of the space that is saved.

This is the ideal solution:

 1: class Solution:
 2: │   def threeSum(self, nums: List[int]) -> List[List[int]]:
 3: │   │   nums.sort()
 4: │   │   triplets = []
 5: │   │   n = len(nums)
 6: │   │   for first_idx in range(n):
 7: │   │   │   # can skip duplicates for first_idx
 8: │   │   │   if first_idx > 0  and nums[first_idx] == nums[first_idx - 1]:
 9: │   │   │   │   continue
10: │   │   │   │
11: │   │   │   # now, find 2 sum for target = complement:
12: │   │   │   left, right = first_idx + 1, n - 1
13: │   │   │   complement = -nums[first_idx]
14: │   │   │   while left < right:
15: │   │   │   │   partial_sum = nums[left] + nums[right]
16: │   │   │   │   # case 1: found a triplet:
17: │   │   │   │   if partial_sum == complement:
18: │   │   │   │   │   triplets.append([nums[first_idx], nums[left], nums[right]])
19: │   │   │   │   │   # skip duplicates for the other pointers, as much as possible:
20: │   │   │   │   │   while(can_skip_duplicate_lefts:= left < right and nums[left] == nums[left + 1]):
21: │   │   │   │   │   │   left += 1
22: │   │   │   │   │   while(can_skip_duplicate_rights:= left < right and nums[right] == nums[right - 1]):
23: │   │   │   │   │   │   right -= 1
24: │   │   │   │   │   │
25: │   │   │   │   │   # converge pointer as per normal
26: │   │   │   │   │   left += 1
27: │   │   │   │   │   right -= 1
28: │   │   │   │   │
29: │   │   │   │   # case 2: need to move the left point to attempt to get a bigger sum:
30: │   │   │   │   elif (partial_sum < complement):
31: │   │   │   │   │   left += 1
32: │   │   │   │   │
33: │   │   │   │   # case 3: partial sum > complement, need to make the partial sum smaller, so we move the right pointer
34: │   │   │   │   else:
35: │   │   │   │   │   right -= 1
36: │   │   │   │   │
37: │   │   return triplets

Complexity:

• runtime: \(O(n^2)\) since it’s a 2 pointer solution
• space: \(O(1)\) since it’s in-place an nothing extra gets used

The key idea here is that we just want to find a,b,c and to do that we have to fix a and find the pairs b,c. So the 2-pointer 2 sum approach works great here. From the previous experiences on running 2-sum on sorted (non-decreasing) arrays will give the intuition to pre-process (sort) the input array (in-place) first.

This is the most optimal approach already and compared to the Hash-based approach, this has significant space-savings.

1. initial approach: I was trying to reduce it to a two-sum problem so I can just run it on 2-sum. While this is valid, the use of the aux data structures is space-wasting.

1. 2-pointer solutions are exceptionally space-saving. We should keep that in mind always. For them to work well, sorting as a pre-processing step would be useful so that their sorted properties can be exploited.
2. Sorting can actually be a first-reach approach here. We should have the intuition on what kind of runtime we can expect. In this case, the original 2 sum can be done in \(O(n)\) time. We expect this to be slower than that, and \(O(n^2)\) is a reasonable expectation because it’s almost like a dimension higher. In that case, it makes sense to take a \(O(n logn)\) “performance hit” from pre-processing the list by sorting it first.

1. we need to pick two possible locations for container walls, the other walls don’t exist yet, they are just options
2. we need to just return the max value, no indices needed

Here’s the stuff I do know:

1. the use of “water” is intentional, but in this case the pillars don’t pre-exist so we don’t need to care about a subset area filling up differently from the rest
2. The analogy for this is like that of a rubberband iirc, but I can’t imagine how the searching would be fair or how to make the right greedy judgement
3. As a 2-pointer solution, we expect the performance to be \(O(n)\) speed and \(O(1)\) space
4. I know that it’s greedily decided but What I’m missing is the greedy insight: when do we restrict?

1. is this even greedily determined?
2. the init for a max accumulating variable doesn’t always have to be -float('int'). In this case, because it’s array and that value can’t be negative, then we can set the initial value to 0.
3. We can actually just focus on finding out what the greedy property would be – how to make the best locally good decision? That should give us insight.
4. the point on different approaches: Are There Completely Different Approaches? Data structures: No. There is no known O(n log n) or O(n) solution using stacks, heaps, or segment trees for this problem. The two-pointer greedy approach is optimal. Why not DP? The problem’s structure doesn’t allow for meaningful subproblem reuse. Why not monotonic stack? That’s useful for “largest rectangle in histogram” but not here, because both endpoints are variable.

1. they aren’t asking to pick some optimal state, it’s about accumulating some water and geting the most amount out

1. Need to figure out when water gets trapped:
   • when it’s within a valley
   • the amount of water depends on the best height to the right and the best height to the left – how deep the valley is so for any particular spot, we need to keep track of max left and max right ( to find out how deep the valley is)
   • we measure the accumulation by accumulating block by block so for each block i what the water level is going to be above it.
   • water level above block i is determined by the shorter of these two max blocks (max left, max right)

1. learning: the empty cases can really just be early returned – this helps improve timings compared to the population.
2. Don’t get stumped by the related questions on this. The question was to find total accumulation, not the best choice or biggest valley. This means the success rate for each question is still based on the ability to break it down, not some guesswork.

3. Alternative approaches: Stack-based: As above, this approach is more general and useful for histogram problems, but for this specific problem, the two-pointer approach is preferred for its O(1) space

   DP with precomputed arrays: Useful if you need to know left/right max for each position for other reasons, but not as space-efficient as two pointers

   1. Precompute Left/Right Max Arrays (DP)

      Idea: For each position, precompute the tallest bar to the left and right.

      Time: O(n)

      Space: O(n) (for two extra arrays)

      How:

      Scan left-to-right to fill left_max[i].

      Scan right-to-left to fill right_max[i].

      For each position, trapped water is min(left_max[i], right_max[i]) - height[i]

      .

   2. Stack-Based Solution

      Idea: Use a stack to keep track of bars that are bounded by taller bars.

      Time: O(n)

      Space: O(n)

      How:

      Iterate through the array.

      When you find a bar taller than the bar at the top of the stack, pop from the stack and calculate trapped water

      .

• General Intuition on Monotonic stack pattern. It seems that usually, the in-consideration elements are the ones that we’re putting in the stack. They’re in there because we need to preserve some intermediate order of these in-consideration elements.
  • in some cases, we’re putting the unresolved elements in the monotonic stack.
  • this is also useful when we want to keep a history of considerations while we find boundaries for things. The history point rings true here.

  • the stack could also be the currently accumulated best value (e.g. like in the remove duplicates question)

    Show/Hide Md Code

    │ Your intuition is exactly right, and it’s echoed in the literature on monotonic stacks:
    │
    │ - **The stack holds "unresolved" elements**—those for which you haven’t yet found the next smaller (or greater) element.
    │ - **History preservation:** The stack acts as a memory of the indices (or values) of elements that are still "waiting" for their boundary to be found. As you process each new element, you check if it resolves the boundary for any of the elements in the stack[1][2][3].
    │
    │ ### Why keep unresolved elements in the stack?
    │ - **Boundary finding:** For problems like "next smaller/greater element," you need to know, for each element, when a boundary (i.e., a smaller/greater bar) is encountered. You can't know this until you see a bar that breaks the monotonic property.
    │ - **Efficient processing:** By keeping a stack of unresolved elements, you process each element only when its boundary is found, ensuring O(n) time[1][2][3].
    │ - **Order preservation:** The stack maintains a partial order (monotonically increasing or decreasing), which is crucial for efficiently determining boundaries.
    │
    │ ### Example: Largest Rectangle in Histogram
    │ - As you sweep through the histogram, each bar is pushed onto the stack if it hasn't yet found a right boundary (a bar shorter than itself).
    │ - When you find a shorter bar, you pop from the stack, resolving the right boundary for the popped bar. The element below in the stack is the left boundary.
    │ - The stack thus "remembers" all the bars for which you haven't yet found a right boundary.
    │
    │ > “Monotonic stacks are ideal for problems where you need to find the ‘next’ element based on specific criteria, like the next greater element. They are also effective for dynamically maintaining the maximum or minimum element in a changing window. ... By dynamically removing irrelevant elements and preserving a monotonic order, they enable efficient solutions to problems that might otherwise be much slower.”[2]
    │
    │ ### General Principle
    │ - **The stack is a history of candidates**: It holds all elements still waiting for their answer (boundary), and as soon as the answer is found, they're popped and processed.
    │ - **This pattern is powerful** for a wide range of problems involving "next" or "previous" constraints (e.g., next greater/smaller, sliding window maximum/minimum)[1][2][3].
    │
    │ **References:**
    │ [1] algo.monster: Monotonic Stack/Queue Intro
    │ [2] teddysmith.io: Simplify Algorithm Design with the Monotonic Stack Pattern
    │ [3] GeeksforGeeks: Introduction to Monotonic Stack
    │
    │ [1] https://algo.monster/problems/mono_stack_intro
    │ [2] https://teddysmith.io/monotonic-stack-algorithm-pattern/
    │ [3] https://www.geeksforgeeks.org/dsa/introduction-to-monotonic-stack-2/
    │ [4] https://en.wikipedia.org/wiki/Sorting_algorithm
    │ [5] https://stackoverflow.com/questions/72625101/how-do-i-solve-it-with-a-monotonic-stack
    │ [6] https://labuladong.online/algo/en/data-structure/monotonic-stack/
    │ [7] https://en.wikipedia.org/wiki/Monotonic_function
    │ [8] https://liuzhenglaichn.gitbook.io/algorithm/monotonic-stack
    │ [9] https://blog.devgenius.io/monotonic-stack-algorithm-pattern-7bfac59157c2?gi=5dccec2461a5
    │ [10] https://stackoverflow.com/questions/77878403/finding-all-sequences-with-same-stack-operations-to-make-monotonic-stack-from-th
    

• remember to allow every option to be considered (e.g. to be inserted into the monotonic stack). If necessary, we can intentionally iterate until out of range and add a sentinel value for our ease.

  This point comes from how we did so for the largest rectangle question.

• GOTCHA: division “truncates towards zero”

  One pitfall is in not realising the division is described to be “tend to zero” instead of “tend to infinity” In Python, / does floor division, which always rounds towards negative infinity. The problem statement for Evaluate Reverse Polish Notation (LeetCode 150) specifies that division between two integers should truncate towards zero, not negative infinity. For example, =-7 / 2 = -4, but the answer should be -3.

  We can do this instead: '/': lambda a, b: int(a / b) # IMPORTANT:truncates towards zero

1. they give us the matching algo already, we just have to implement it