Two Pointers Intro

LeetCode problems with solutions using two pointers.

What are Two Pointers

Two Pointers is the strategy of using a left and right pointer to iterate over a data structure, usually an array, to solve a problem.

Two Pointers Application: One Pointer with Auxiliary State

We can use a single pointer to iterate linearly and have a second variable to keep track of some state or action.

Ex: Find the maximum consecutive ones in an array

    def max_consecutive_ones(nums: list[int]) -> int:

        # Aux state: track current streak
        count = 0

        # Aux state: track max streak
        max_count = 0

        # Left Pointer: iterate array
        for right in range(len(nums)):
            
            # Condition: while consecutive 1's is true
            if nums[right] == 1:
                # Aux state: add to streak
                count += 1
                max_count = max(max_count, count)
            else:
                # Aux state: reset streak
                count = 0

        return max_count

    # max_consecutive_ones([1,1,0,1,1,1]) -> 3

Two Pointers Application: Opposite Ends

We can have two pointers, left and right, starting at opposite ends of a list and move them inward while validating some sort of logic, stopping when their indexes hit left == right at the middle of the array

Ex: Determine if a string is a palindrome

    def is_palindrome(s: str) -> bool:

        # Left: start of array
        # Right: end of array
        left, right = 0, len(s) - 1

        # Break when left and right pointers match 
        # when the middle of the array is hit
        while left < right:

            # if palindrome invariant is broken
            if s[left] != s[right]:
                return False

            # shrink left and right pointers towards middle
            left += 1
            right -= 1

        # valid palindrome
        return True

    # is_palindrome("radar") -> True
    # is_palindrome("hello") -> False

Two Pointers Application: Sliding Window

We can have two pointers represent a imaginary window, [Left, Right], over a sequence that expands or shrinks while iterating or checking if a condition is satisfied.

Ex: Find the length of the longest substring without repeating characters.

    def longest_unique_substring(s: str) -> int:

        # Left: start of window
        left = 0

        # Window data: stores unique chars within window range
        char_set = set()

        # Window data: stores max window found up to now
        maxLength = 0

        # Right: end of window, expand window range as we iterate
        for right in range(len(s)):

            # Invariant: window holds list of unique chars
            # Broken: if condition is broken, shrink window from the 
            # left side until the unique char condition is true again
            while s[right] in char_set:

                # Window data: remove char on left boundary of window
                char_set.remove(s[left])
                
                # Left: start of window, shrink window range
                left += 1
            
            # Invariant: window holds list of unique chars

            # Window data: add char unique list, guaranteed to be unique
            char_set.add(s[right])
  
            # Window data: check global max
            maxLength = max(maxLength, right - left + 1)

        return maxLength

    # longest_unique_substring("abcabcbb") -> 3

Two Pointers Application: Fast & Slow Pointers

We can traverse linked lists using pointers. In this case two pointers moving at different speeds x1 and x2 can detect cycles or find midpoints in linked lists or arrays.

Ex: Detect a cycle in a linked list.


    # linked list node definition
    class ListNode:
        def __init__(self, value=0, next=None):
            self.value = value
            self.next = next

    def has_cycle(head: ListNode) -> bool:
        
        # Tortoise, hare pointers: same starting index
        slow, fast = head, head

        while fast and fast.next:

            # Tortoise pointer: x1 steps
            # Hare pointer: x2 steps
            slow = slow.next
            fast = fast.next.next

            # if pointers match, cycle exists
            # will be hit a n/2 iterations
            if slow == fast:
                return True

        # reached end of list, no cycles
        return False

    # LinkedList: 1 -> 2 -> 3 -> 4 -> 2
    # has_cycle(head) -> True

Two Pointers Application: Lomuto Partition

We can have two pointers in the same array moving inward/outward to rearrange elements based on a condition.

Ex: Lomuto partition scheme in quicksort

    def partition(nums, pivot):

        # Left: partition flip slot
        left = 0

        # Right: iterate array checking condition
        for right in range(len(nums)):

            # Condition: if curr element value is less than pivot val, 
            # flip element to left side of array in place
            if nums[right] < pivot:

                # Flip: swap element with flip slot
                nums[left], nums[right] = nums[right], nums[left]

                # Left: iterate flip slot by 1 step
                left += 1

        # Left: ends up pointing to first index where all elements 
        # are greater than the pivot value
        return (nums, left)

    # partition([9, 3, 5, 2, 8, 1, 6], 5) -> ([3, 2, 1, 5, 8, 9, 6], 5)

Two Pointers Application: Parallel Array Pointer Traversal

We can expand our previous application cards to use k pointers traversing separate k arrays in parallel to merge, compare, find intersections, or other patterns.

Ex: Merge two sorted arrays into one sorted array

    def merge_sorted_arrays(arr1, arr2):

        result = []

        # i / j: 2 pointers
        i, j = 0, 0

        # i / j: parallel iterate array, while elements remain in both lists 
        while i < len(arr1) and j < len(arr2):

            # Merge: append smaller element between arrays 
            if arr1[i] < arr2[j]:
                result.append(arr1[i])
                i += 1
            else:
                result.append(arr2[j])
                j += 1
        
        # Merge: one list has run out of elements, 
        # append list with remaining elements as its already sorted
        result.extend(arr1[i:])
        result.extend(arr2[j:])

        # merged sorted array
        return result

    # merge_sorted_arrays([1, 3, 5], [2, 4, 6]) -> [1, 2, 3, 4, 5, 6]

Two Pointers Application: Catchup Pointer

We can have two pointers traversing an array. The left pointer can be responsible for being frozen until the right pointer hits a delimiter, at which point some logic executes, then left jumps 'catches up' but jumping to right+1 to mark the start of the next section/iteration.

Ex: Split string by spaces

    def split_words(s: str, delim: str = ' ') -> list[str]:

        words = []

        # Left: frozen until right hits delim
        left = 0

        # Right: iterate list checking for delim
        right = 0

        # Right: iterate list
        while right < len(s):

            # Right condition: delimiter found
            if s[right] == delim:

                # Logic: check if non-empty word, 
                # then splice word and add to array
                if left != right:
                    words.append(s[left:right])

                # Left: Catch up, move to right+1, to 1 index
                # after the delimiter, to restart scanning for delim
                left = right + 1

            # Right: iterate pointer, either after delim
            # or to next index
            right += 1

        # Right: hit end of string, check if last word exists
        if left < len(s):
            words.append(s[left:])

        return words


    # split_words("catch up pointers example") -> ['catch', 'up', 'pointers', 'example']

Two Pointers Application: K Pointer Variants

We can extend the two pointers to k pointers. These pointers could follow any of the pointer applications, traverse the same list, different lists, freeze while moving others, etc.

Ex: Given array, return unique triplets [nums[i], nums[j], nums[k]] that sum to 0.

    def threeSum(nums):

        result = []
        nums.sort()

        # k: 3 pointers, i, left, right

        # i: iterate pointer as 'frozen' pointer
        for i in range(len(nums)):

            # i: Avoid duplicates
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # Inner two pointer approach:

            # Left: 1 index after frozen pointer
            # Right: right end of array
            left, right = i + 1, len(nums) - 1
            while left < right:

                # Condition: check if triplet sum == 0
                current_sum = nums[i] + nums[left] + nums[right]                
                if current_sum == 0:

                    # Match: add triplet
                    result.append([nums[i], nums[left], nums[right]])

                    # Left / Right: Iterate to avoid duplicates
                    left += 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    right -= 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

                # Search: 
                # left end has lowest numbers, right end has highest numbers,
                # shift towards whichever gets triplet sum closer to 0

                # Left: shift towards higher numbers
                elif current_sum < 0:
                    left += 1 

                # Right: shift towards lower numbers 
                else:
                    right -= 1

        return result

    # threeSum([-1, 0, 1, 2, -1, -4]) -> [[-1, -1, 2], [-1, 0, 1]]

Two Pointers Application: Algorithm

We can have cases where problems that seems to require two pointers have an algorithm specifically made for that problem.

Ex: Manacher's Algorithm, longest palindromic substring

    def longestPalindrome(s: str) -> str:

        # Preprocess the string to handle even length palindromes
        t = "#".join(f"^{s}$")
        n = len(t)
        p = [0] * n
        center = right = 0

        
        for i in range(1, n - 1):

            # Mirror of `i` with respect to `center`
            mirror = 2 * center - i

            # If within bounds of the current right boundary, use mirror head start 
            if i < right:
                p[i] = min(right - i, p[mirror])

            # Expand around 'i' while palindrome condition true
            while t[i + p[i] + 1] == t[i - p[i] - 1]:
                p[i] += 1

            # Update the center and right boundary if the palindrome is expanded
            if i + p[i] > right:
                center = i
                right = i + p[i]

        # Find the maximum length palindrome
        maxLen, centerIndex = max((n, i) for i, n in enumerate(p))

        # Convert index back to original string
        start = (centerIndex - maxLen) // 2
        
        # Grab palindrome substring
        return s[start: start + maxLen]

125. Valid Palindrome ::3:: - Easy

Topics: Two Pointers, String

Intro

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise.

Input	Output
"A man, a plan, a canal: Panama"	true
"race a car"	false
" "	true

Constraints:

string s consists only of printable ASCII characters.

Abstraction

Using two pointers, L and R, we can traverse the string validating palindrome status as we iterate.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark
Two Pointer	O(n)	O(n)	Iterate over string of n length O(n)	Memory allocation for cleaned list of n length O(n)
Two Pointer In Place	O(n)	O(1)	Iterate over string of n length O(n)	No additional memory allocation for in place comparison O(1)

Bug: Used Less than Instead of Less than or equal to

def isPalindrome(self, s: str) -> bool:

        # BUG:
        # not including outer characters
        def isAlphaNum(c):
            return (ord('a') < ord(c) < ord('z') or
                    ord('A') < ord(c) < ord('Z') or
                    ord('0') < ord(c) < ord('9'))

        # BUG:
        # not including outer characters
        def isUpper(c):
            return (ord('A') < ord(c) < ord('Z'))

        def toLower(c):
            return chr(ord(c) + 32)

        cleaned = []

        for c in s:
            if isAlphaNum(c):
                if isUpper(c):
                    cleaned.append(toLower(c))
                else:
                    cleaned.append(c)

        left, right = 0, len(cleaned)-1

        while left < right:
            if cleaned[left] != cleaned[right]:
                return False

            left += 1
            right -=1 

        return True

Bug: Not Moving Pointers In 1 of 2 Cases

    def isPalindrome(self, s: str) -> bool:

        def isAlphaNum(c):
            return (ord('a') <= ord(c) <= ord('z') or
                    ord('A') <= ord(c) <= ord('Z') or
                    ord('0') <= ord(c) <= ord('9'))

        def isUpper(c):
            return ord('A') <= ord(c) <= ord('Z')

        def toLower(c):
            return chr(ord(c) + 32)

        l, r = 0, len(s)-1

        while l < r:

            # INCORRECT:
            # 2nd iteration, if s[l] or s[r] is AlphaNum
            # pointers will not enter loop and will not += or -=
            while l < r and not isAlphaNum(s[l]):
                l += 1
            while l < r and not isAlphaNum(s[r]):
                r -= 1
        
            leftChar = s[l]
            rightChar = s[r]

            if isUpper(leftChar):
                leftChar = toLower(leftChar)
            if isUpper(rightChar):
                rightChar = toLower(rightChar)

            if leftChar != rightChar:
                return False

            # INCORRECT: we are missing 
            # l += 1
            # r -= 1
            # we are assuming that the inner 2 while loops will do the job,
            # but the pointers never iterate.
            # Instead, we will keep grabbing the current iteration
            # and get into an infinite loop
        return True

Bug: Missing Char Palindrome Comparison, im half sleep ok give me a break :')

    def isPalindrome(self, s: str) -> bool:

        def isAlphaNum(c):
            return (ord('a') <= ord(c) <= ord('z') or
                    ord('A') <= ord(c) <= ord('Z') or
                    ord('0') <= ord(c) <= ord('9'))

        def isUpper(c):
            return ord('A') <= ord(c) <= ord('Z')

        def toLower(c):
            return chr(ord(c) + 32)

        l, r = 0, len(s)-1

        while l < r:
            while l < r and not isAlphaNum(s[l]):
                l += 1
            while l < r and not isAlphaNum(s[r]):
                r -= 1
        
            leftChar = s[l]
            rightChar = s[r]

            if isUpper(leftChar):
                leftChar = toLower(leftChar)
            if isUpper(rightChar):
                rightChar = toLower(rightChar)

            # BUG:
            # missing palindrome validation

            l += 1
            r -= 1
        return True

Solution 1: [::-1] Reverse Slice Comparison - Two Pointers/Algorithm

    def isPalindrome(self, s: str) -> bool:
        
        # sc: cleaned version of string O(n)
        clean = []

        # tc: iterate string O(n)
        for c in s:

            # only compare alphaNum
            if c.isalnum():
                clean.append(c.lower())
        
        # tc: join list O(n)
        clean = "".join(clean)

        # Slicing -> [::-1]
        # [start:stop:step]
        # -----------------
        # if start and stop are omitted, slice includes the entire sequence
        # step is -1, indicates to traverse in reverse

        # tc: iterate over two strings comparing
        # sc: create separate reversed string
        res = phrase == phrase[::-1]

        # overall: tc O(n)
        # overall: sc O(n)
        return

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Clean string	O(n)	O(n)	Iterate string O(n), append O(1), join O(n)	Allocation for clean string O(n)
Palindrome Check	O(n)	O(n)	Slice reverse O(n), comparison O(n)	Slice allocates reversed string O(n)
Overall	O(n)	O(n)	Iterate string dominates, O(n)	Allocation for clean string dominates, O(n)

Solution 2: Clean Opposite Ends - Two Pointers/Opposite Ends

    def isPalindrome(self, s: str) -> bool:
        
        # sc: cleaned string O(n)
        cleaned = []

        # helper: check if isAlphaNum
        def isAlphaNum(c):
            return (ord('A') <= ord(c) <= ord('Z') or 
                    ord('a') <= ord(c) <= ord('z') or 
                    ord('0') <= ord(c) <= ord('9'))

        # helper: check if uppercase
        def isUpper(c):
            return ord('A') <= ord(c) <= ord('Z')

        # helper: shift upper to lowercase
        def toLower(c):
            return chr(ord(c) + 32)

        # tc: iterate string O(n)
        for c in s:

            # Condition: only compare isAlphaNum
            if isAlphaNum(c):
                
                # Condition: only compare lowercase
                if isUpper(c):
                    cleaned.append(toLower(c))
                else:
                    cleaned.append(c)

        # tc: iterate clean list O(n)
        left, right = 0, len(cleaned) - 1
        while left < right:

            # Condition: validate palindrome
            if cleaned[left] != cleaned[right]:
                return False

            # Left/Right: shrink pointers towards center
            left += 1
            right -= 1

        # overall: tc O(n)
        # overall: sc O(n)
        return True

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Cleaned string	O(n)	O(n)	Iterate string O(n)	Allocation for clean string O(n)
Two Pointer	O(n)	O(1)	Compare char pairs O(1) for n/2 steps O(n)	No allocation O(1)
Overall	O(n)	O(n)	Iterate string dominates, O(n)	Allocation for clean string dominates, O(n)

Solution 3: In Place Opposite Ends - Two Pointers/Opposite Ends

    def isPalindrome(self, s: str) -> bool:

        # helper: check if isAlphaNum
        def isAlphaNum(c):
            return (ord('A') <= ord(c) <= ord('Z') or 
                    ord('a') <= ord(c) <= ord('z') or 
                    ord('0') <= ord(c) <= ord('9'))

        # helper: check if uppercase
        def isUpper(c):
            return ord('A') <= ord(c) <= ord('Z')

        # helper: shift upper to lowercase
        def toLower(c):
            return chr(ord(c) + 32)

        # sc: no additional space used for storage O(1)

        # tc: iterate string O(n)
        left, right = 0, len(s) - 1
        while left < right:
            
            # Condition: only compare alphaNum
            while left < right and not isAlphaNum(s[left]):
                left += 1
            while left < right and not isAlphaNum(s[right]):
                right -= 1

            # grab pointer values
            leftChar = s[left]
            rightChar = s[right]

            # Condition: only compare lowercase
            if isUpper(leftChar):
                leftChar = toLower(leftChar)
            if isUpper(rightChar):
                rightChar = toLower(rightChar)

            # Condition: validate palindrome
            if leftChar != rightChar:
                return False

            # Left/Right: shrink pointers towards center
            left += 1
            right -= 1

        # overall: tc O(n)
        # overall: sc O(1)
        return True

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Two Pointer	O(n)	O(1)	Iterate string O(n), compare alphaNum pairs O(1)	No allocation O(1)
Overall	O(n)	O(1)	Iterate string dominates, O(n)	No allocation O(1)

271. String Encode and Decode ::2:: - Medium

Topics: Two Pointers, Design

Intro

Design an algorithm to encode a list of strings to a single string and a decode algorithm to decode the single string back to the original list of strings, strs[i] contains only UTF-8 characters.

Input	Output
["leet", "code", "love", "you"]	["leet", "code", "love", "you"]
["we", "say", ":", "yes"]	["we", "say", ":", "yes"]

Constraints:

string s contains only UTF-8 characters

Abstraction

Create an encode and decode function to encode a list to a string, and a string back to the original list.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark
Splicing Delimiter with Catchup 2 pointers	O(n * m)	O(n * m)	Linear iteration for encode and decode across all strings and chars dominates, O(n * m)	Allocation for encoded and decoded strings dominates, O(n * m)
Base 10 Auxiliary Length Delimiter with 1 pointer	O(n * m)	O(n * m)	Linear iteration for encode and decode across all strings and chars dominates, O(n * m)	Allocation for encoded and decoded strings dominates, O(n * m)

Bug: Decoded Length + Delimiter (Grabbed str(len) instead int(len))

    def decode(self, encoded: str) -> List[str]:

        # space complexity: list of n strings O(n) each of n length O(n), leading to O(n^2)
        decoded = []
        left = 0

        # time complexity: iterate over representation of n strings O(n) each of n length O(n), leading to O(n^2)
        while left < len(encoded):

            # grab length prefix behind "#" delimiter
            right = left
            while encoded[right] != "#":
                right += 1

            # splicing the length of the string
            # BUG: 
            # length is a string, cannot use it to index or add
            # need to use int()
            length = encoded[left:right]

            # skip delimiter, point to start of string
            right += 1

            # splicing the string of 'length' characters
            # time complexity: splice over string n length O(n) for n iterations O(n), leading to O(n^2)
            decoded.append(encoded[right:right + length])

            # skip string, point to start of next len
            left = right + length

        # overall: time complexity O(n^2)
        # overall: space complexity O(n^2)
        return decoded

Bug: Decoded Base 10 doing += instead of = (half asleep)

    def decode(self, encoded: str) -> List[str]:
        
        # base 10 strategy 
        # or 2 pointer splice strategy

        decoded = []
        left = 0

        while left < len(encoded):

            # grab length before delim
            currLen = 0
            while encoded[left] != "#":

                # BUG:
                # we need to update currLen, not add to it
                currLen += (10*currLen) + int(encoded[left])
                left += 1
            
            # step past delim
            left += 1
            substring = []

            for _ in range(currLen):
                substring.append(encoded[left])
                left += 1

            decoded.append(''.join(substring))

        return decoded

Solution 1: Splicing Delimiter with Catchup 2 pointers - Two Pointers/Catchup

    def encode(self, strs: List[str]) -> str:

        # Note: 
        # python strings are immutable so concatenation with += "" 
        # python creates new string quadratically
        # the efficient alternative:
        # python list .append() modifies list in place by adding a single
        # element at end in O(1) operation
        # after appending all chars a "".join() in O(n)
        # creates the same string in better time complexity

        # sc: n strings with m chars O(n * m)
        encoded = []

        # tc: iterate list O(n)
        for s in strs:
            
            # tc: lenDelim length proportional to log10(m) ~= O(1)
            # append "{length}#" -> "5#""
            lenDelim = str(len(s)) + "#"
            left = 0
            while left < len(lenDelim):
                encoded.append(lenDelim[left])
                left += 1
            
            # tc: iterate string O(m)
            # append each char
            left = 0
            while left < len(s):
                encoded.append(s[left])
                left += 1
        
        # overall: tc O(n * m)
        # overall: sc O(n * m)
        return ''.join(encoded)


    def decode(self, encoded: str) -> List[str]:

        # sc: n strings with m chars O(n * m)
        decoded = []
        left = 0

        # tc: iterate string encoding of list O(n * m)
        while left < len(encoded):

            # Right: set to start of length prefix
            right = left

            # tc: log 10 (m) ~= O(1)
            # Right: shift until pointing to delimiter
            while encoded[right] != "#":
                right += 1

            # after:
            # [ 2 # h i ... ]
            #   ^ ^
            #   l r 

            # slice out string length
            length = int(encoded[left:right])

            # skip delimiter, point to start of string
            right += 1

            # after:
            # [ 2 # h i ... ]
            #   ^   ^
            #   l   r 

            # tc: slice out substring of length m 
            decoded.append(encoded[right:right + length])
           
            left = right + length
            
            # Left: shift to start of next length prefix
            # [ 2 # h i 4 # ...]
            # [ 0 1 2 3 4 5 6 ...]
            #       ^   ^
            #       r   l

        # overall: tc O(n * m)
        # overall: sc O(n * m)
        return decoded

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Encode loop	O(n * m)	O(n * m)	Iterate n strings of m length dominates, O(n * m)	Allocation for encoded string dominates, O(n * m)
Decode loop	O(n * m)	O(n * m)	Iterate over encoded string of n strings of m length dominates, O(n * m)	Allocation for decoded list of n strings of m length O(n * m)
Overall	O(n * m)	O(n * m)	Linear iteration for encode and decode across all strings and chars dominates, O(n * m)	Allocation for encoded and decoded strings dominates, O(n * m)

Solution 2: Base 10 Auxiliary Length Delimiter with 1 pointer - Two Pointers/One Pointer with Auxiliary State

    def encode(self, strs: List[str]) -> str:

        # Note: 
        # python strings are immutable so concatenation with += "" 
        # python creates new string time complexity o(n^2)
        # python list .append() modifies list in place by adding a single
        # element at end in O(1) operation
        # so doing .append() with a "".join() at the end is more efficient  

        # space complexity: for n strings O(n) store n characters O(n), leading to O(n^2)
        encoded = []

        # time complexity: iterate over list of strings n length O(n)
        for s in strs:
            
            # lenDelim = len + delim
            lenDelim = str(len(s)) + "#"

            # append length and delimiter "5#"
            left = 0
            while left < len(lenDelim):
                encoded.append(lenDelim[left])
                left += 1
            
            # append string itself
            # time complexity: iterate over string of n length O(n), for n iterations, leading to O(n^2)
            left = 0
            while left < len(s):
                encoded.append(s[left])
                left += 1
        
        # overall: time complexity O(n^2)
        # overall: space complexity O(n^2)
        return ''.join(encoded)


    def decode(self, encoded: str) -> List[str]:

        # space complexity: list of n strings O(n) each of n length O(n), leading to O(n^2)
        decoded = []
        left = 0

        # time complexity: iterate over representation of n strings O(n) each of n length O(n), leading to O(n^2)
        while left < len(encoded):

            # grab length prefix behind "#" delimiter
            currLen = 0
            while encoded[left] != "#":

                # grabbing value while calculating base 10 of prev
                currLen = currLen * 10 + int(encoded[left]) 
                left += 1

            # skip delimiter, point to start of string
            left += 1  

            # extract substring of 'currLen' characters
            # time complexity: iterate over string n length O(n) for n iterations O(n), leading to O(n^2)
            substring = []
            for _ in range(currLen):

                # forming string
                substring.append(encoded[left])
                left += 1
            
            # left is pointing to start of next len

            # add string to decoded list of strings
            decoded.append(''.join(substring))


        # overall: time complexity O(n^2)
        # overall: space complexity O(n^2)
        return decoded

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Encode loop	O(n * m)	O(n * m)	Iterate n strings of m length dominates, O(n * m)	Allocation for encoded string dominates, O(n * m)
Decode loop	O(n * m)	O(n * m)	Iterate over encoded string of n strings of m length dominates, O(n * m)	Allocation for decoded list of n strings of m length O(n * m)
Overall	O(n * m)	O(n * m)	Linear iteration for encode and decode across all strings and chars dominates, O(n * m)	Allocation for encoded and decoded strings dominates, O(n * m)

167. Two Sum II Sorted Array ::2:: - Medium

Topics: Array, Two Pointers, Binary Search

Intro

Given a 1 indexed array of sorted integer in non decreasing order, find two numbers that add up to a target. Let these two numbers be numbers[index1] and numbers[index2] where 1 ≤ index1 < index2 ≤ numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice.

Input List	Input Target	Output
[2, 7, 11, 15]	9	[1,2]
[2, 3, 4]	6	[1,3]
[-1, 0]	-1	[1,2]

Constraints:

Solutions can only use constant space O(1)

Abstraction

Given a sorted array, find two numbers that add up to target, and numbers cannot share indexes.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark
Binary Search for Complement	O(n log n)	O(1)	Iterates over list of n elements O(n), performing binary search on each O(log n) leading to O(n log n)	No additional memory allocation O(1)
Two Pointers	Iterates through array of n length using two pointers O(n)	No additional memory allocation O(1)

Bug: Binary Search updates left and right pointer by midValue instead of midIndex

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
       
        for i in range(len(numbers)):
            currComplementTarget = target - numbers[i]

            left, right = i + 1, len(numbers) - 1
            
            while left <= right:

                midIndex = (left + right)//2
                midInt = numbers[midIndex]

                if currComplementTarget == midInt:
                    return [i + 1, mid + 1]
                
                # BUG:
                # moving pointer based on int value, instead of index
                elif currComplementTarget < midInt:
                    right = midInt - 1

                # BUG:
                # moving pointer based on int value, instead of index
                else:
                    left = midInt + 1
        
        return []

Solution 1: BinarySearch Per Element for Complement - Two Pointers/One Pointer with Auxiliary State

    def twoSumII(self, numbers: List[int], target: int) -> List[int]:
        
        # time complexity: iteration over list of n length O(n)
        for i in range(len(numbers)): 

            # search for complement
            currComplementSearch = target - numbers[i]
            
            # Set up BinarySearch
            # set new left boundary for iteration BinarySearch
            # reset right boundary for iteration BinarySearch
            # given constraint index1 < index2
            # BinarySearch on right section of array after left element
            # time complexity: binarySearch O(log n) for each iteration O(n), leading to O(n log n)
            left, right = i + 1, len(numbers) - 1
            
            # BinarySearch
            # "<=": working within subarray [i+1, j] separate from i, 
            # so must evaluate num at left == right, as might be currComplementSearch
            # Base Case: no more array remaining to search
            # complement for numbers[i] was not found, continue iteration
            while left <= right:
                
                # middle element
                midIndex = (left + right) // 2
                midNum = numbers[midIndex]

                # found target complement
                if midNum == currComplementSearch:
                    # convert to 1-indexed array, per input/output example
                    return [i + 1, midIndex + 1]  

                # "BinarySearch" on relevant subsection
                # update left or right pointer
                elif midNum < currComplementSearch:
                    left = midIndex + 1
                else:
                    right = midIndex - 1

        # overall: time complexity O(n log n)
        # overall: space complexity O(1)
        return []

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Outer loop	O(n)	O(1)	Iterates over list of n length O(n)	No additional memory allocation for iteration O(1)
Binary Search	O(log n)	O(1)	Binary search over array for complement O(log n)	No additional memory allocation for binary search O(1)
Overall	O(n log n)	O(1)	Binary search for each element dominates leading to O(n log n)	No additional memory allocation leading to constant O(1).

Solution 2: Opposite Ends Pointer Shift by BinarySearch Modification for Target - Two Pointers/Opposite Ends

    def twoSumII(self, numbers: List[int], target: int) -> List[int]:

        # Set up BinarySearch Modification
        # initialize outer pointers
        # space complexity: left and right pointers constant O(1)
        left, right = 0, len(numbers) - 1  

        # BinarySearch Modification
        # "<": working within subarray containing left and right
        # cannot evaluate num at left == right, breaks constraints of index1 < index2
        # Base Case: no more array remaining to search, 
        # return []
        # time complexity: iterate over list of n length O(n)
        while left < right:

            # grab current sum
            currSum = numbers[left] + numbers[right]  

            # found target sum
            if currSum == target:
                # convert to 1-indexed array, per input/output example
                return [left + 1, right + 1]

            # "BinarySearch" on relevant subsection
            # update left or right pointer
            elif currSum < target:
                left += 1
            else:
                right -= 1

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return []

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Pointer Loop	O(n)	O(1)	Left and right pointers iterate over list of n length O(n)	No additional memory allocation O(1)
Comparison	O(1)	O(1)	Sum and comparison operations take constant O(1)	No additional memory allocation for sum and comparison operations O(1)
Overall	O(n)	O(1)	Iterating with left and right pointers over list of n length dominates leading to O(n)	No additional memory allocation leading to constant O(1)

15. 3Sum ::2:: - Medium

Topics: Array, Two Pointers, Sorting, Binary Search

Intro

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

nums	Output
[-1,0,1,2,-1,-4]	[[-1,-1,2],[-1,0,1]]
[0,1,1]	[]
[0,0,0]	[[0,0,0]]

Constraints:

Abstraction

Given an array find all the groups of 3 integers that add up to 0, without duplicates.

Sorting vs non-sorting is the first distinction which will lead to different solutions.

We can:

Sort by increasing value
Sort by parity

Both of these give us different assumptions we can use to our advantage as we traverse the array. Let see:

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark
Brute Force (all triplets comparison)
Hashmap (Two Sum I Approach)
Two Pointers Set
Two Pointers Early Breaks Set

Brute Force (all triplets comparison)

    def threeSum(self, nums: List[int]) -> List[List[int]]:

        # space complexity: set of unique m triplets tuples O(m)
        res = set() 
        n = len(nums)

        # time complexity: n choose three for all triplet combinations / three nested loops O(n^3)
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    
                    # time complexity: sum and comparison operation in constant O(1)
                    if nums[i] + nums[j] + nums[k] == 0:

                        # time complexity: sorting 3 elements in near constant O(1)
                        triplet = sorted([nums[i], nums[j], nums[k]])
                        
                        # time complexity: insert operation in constant O(1)
                        res.add(tuple(triplet))

        # overall: time complexity O(n^3)
        # overall: space complexity O(,)
        return [list(triplet) for triplet in res]

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Brute Force Hashmap Two Sum I Approach (No Sorting)

    def threeSum(self, nums: List[int]) -> List[List[int]]:
       
        # space complexity: set of unique m triplet tuples O(m)
        n = len(nums)
        res = set()

        # freezing one of the triple tuple values
        # time complexity: iteration over list of n length O(n)
        for i in range(n - 2):

            # grab complement
            target = -nums[i]
            seen = {}      # [ (value → its index), ...]

            # freezing second of the triple tuple values
            # time complexity: iteration over list of n length per outer iteration O(n^2)
            for j in range(i + 1, n):

                # grab complement
                complement = target - nums[j]

                # time complexity: lookup operation in constant O(1)
                if complement in seen:

                    # add unique tuple to res
                    triplet = tuple(sorted((nums[i], nums[j], complement)))
                    res.add(triplet)
                else:
                    seen[nums[j]] = j

        # overall: time complexity  
        # overall: space complexity 
        return [list(t) for t in res]

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug: List is unHashable

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        # Note: Two Sum vs 3Sum
        # Two sum, finding two numbers whose sum equals a target is simple
        # with hashmaps or two pointer approaches being efficient
        # 3Sum adds complexity with a third variable.
        # Grouping techniques aim to narrow and organize the solution space
        # reducing redundant checks while finding valid triplets

        # positive, negative, and zero sets
        # space complexity: 
        p, n, z = [], [], []
        
        # set ensures no duplicate triplets
        # space complexity: 
        res = set()

        # time complexity: iterate over list of n length O(n)
        for i in nums:
            if i < 0:
                n.append(i)
            elif i > 0:
                p.append(i)
            else:
                z.append(i)

        # sets for unique groups
        # time complexity: convert list into set O(n)
        P, N = set(p), set(n)

        # (0, num, -num)
        # time complexity: iterate over positive numbers list n length O(n)
        if len(z) > 0:
            for i in P:                
                # time complexity: negative target lookup in constant O(1)
                nTarget = -i
                if nTarget in N:
                    res.add((nTarget, 0, i))

        # (0, 0, 0)
        # time complexity: len operation constant O(1)
        if len(z) >= 3:
            res.add((0, 0, 0))

        # (-, -, +) negative pairs
        # time complexity: iterate over list of negative numbers n length O(n)
        for i in range(len(n)):
            # time complexity: iterate over list of negative numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(n)):
                # time complexity: lookup operation constant O(1)
                pTarget = -(n[i] + n[j])
                if pTarget in P:
                    # INCORRECT:
                    # sorted() -> List[int]
                    # cannot hash list into set()
                    # must use tuple(sorted())
                    res.add((sorted([n[i], n[j], pTarget])))
        
        # (-, +, +) positive pairs
        # time complexity: iterate over list of positive numbers n length O(n)
        for i in range(len(p)):
            # time complexity: iterate over list of positive numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(p)):
                # time complexity: lookup operation constant O(1)
                nTarget = -(p[i] + p[j])
                if nTarget in n:
                    # INCORRECT:
                    # sorted() -> List[int]
                    # cannot hash list into set()
                    # must use tuple(sorted())
                    res.add(tuple(sorted([p[i], p[j], nTarget])))

        # convert valid set of tuple triplets into valid list of tuple triplets

        # overall: time complexity O(n^2) 
        # overall: space complexity O(n)
        return list(res)

Find the Bug: Index Into Wrong Array (2x) [im half asleep rn ok? :) cut me some slack]

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        # Note: Two Sum vs 3Sum
        # Two sum, finding two numbers whose sum equals a target is simple
        # with hashmaps or two pointer approaches being efficient
        # 3Sum adds complexity with a third variable.
        # Grouping techniques aim to narrow and organize the solution space
        # reducing redundant checks while finding valid triplets

        # positive, negative, and zero sets
        # space complexity: 
        p, n, z = [], [], []
        
        # set ensures no duplicate triplets
        # space complexity: 
        res = set()

        # time complexity: iterate over list of n length O(n)
        for i in nums:
            if i < 0:
                n.append(i)
            elif i > 0:
                p.append(i)
            else:
                z.append(i)

        # sets for unique groups
        # time complexity: convert list into set O(n)
        P, N = set(p), set(n)

        # (0, num, -num)
        # time complexity: iterate over positive numbers list n length O(n)
        if len(z) > 0:
            for i in P:                
                # time complexity: negative target lookup in constant O(1)
                nTarget = -i
                if nTarget in N:
                    res.add((nTarget, 0, i ))

        # (0, 0, 0)
        # time complexity: len operation constant O(1)
        if len(z) >= 3:
            res.add((0, 0, 0))

        # (-, -, +) negative pairs
        # time complexity: iterate over list of negative numbers n length O(n)
        for i in range(len(n)):
            # time complexity: iterate over list of negative numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(n)):
                # time complexity: lookup operation constant O(1)
                # INCORRECT:
                # stop being half asleep, index into the correct array
                pTarget = -(nums[i] + nums[j])
                if pTarget in P:
                    # INCORRECT:
                    # stop being half asleep, index into the correct array
                    res.add(tuple(sorted([nums[i], nums[j], pTarget])))
        
        # (-, +, +) positive pairs
        # time complexity: iterate over list of positive numbers n length O(n)
        for i in range(len(p)):
            # time complexity: iterate over list of positive numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(p)):
                # time complexity: lookup operation constant O(1)
                # INCORRECT:
                # stop being half asleep, index into the correct array
                nTarget = -(nums[i] + nums[j])
                if nTarget in n:
                    # INCORRECT:
                    # stop being half asleep, index into the correct array
                    res.add(tuple(sorted([nums[i], nums[j], nTarget])))

        # convert valid set of tuple triplets into valid list of tuple triplets

        # overall: time complexity O(n^2) 
        # overall: space complexity O(n)
        return list(res)

Find the Bug: Giving Sorted() 3 arguments instead of 1 [i dont know python syntax, YET :)]

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        res = set()
        p, n, z = [], [], []

        for num in nums:
            if num > 0:
                p.append(num)
            elif num < 0:
                n.append(num)
            else:
                z.append(num)

        P, N = set(p), set(n)

        # (0, -k, k)
        if len(z) >= 1:
            for neg in N:
                pos = (-neg)
                if pos in P:
                    res.add((neg, 0, pos))

        # (0, 0, 0)
        if len(z) >= 3:
            res.add((0, 0, 0))

        # (-a, -b, c)
        for i in range(len(n)):
            for j in range (i+1, len(n)):
                pos = -1 * (n[i] + n[j])
                if pos in P:
                    # INCORRECT:
                    # sorted takes 1 argument list of ints,
                    # not 3 arguments
                    res.add(tuple(sorted(n[i], n[j], pos)))

        # (a, b, -c)
        for i in range(len(p)):
            for j in range(i+1, len(p)):
                neg = -1 * (p[i] + p[j])
                if neg in N:
                    # INCORRECT:
                    # sorted takes 1 argument list of ints,
                    # not 3 arguments
                    res.add(tuple(sorted(p[i], p[j], neg)))

        return res

Find the Bug: Adding Set to Set, cannot because set is un-hashable type [again, syntax]

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        res = set()
        p, n, z = [], [], []

        for num in nums:
            if num > 0:
                p.append(num)
            elif num < 0:
                n.append(num)
            else:
                z.append(num)

        P, N = set(p), set(n)

        # (0, -k, k)
        if len(z) >= 1:
            for neg in N:
                pos = (-neg)
                if pos in P:
                    res.add((neg, 0, pos))

        # (0, 0, 0)
        if len(z) >= 3:
            res.add((0, 0, 0))

        # (-a, -b, c)
        for i in range(len(n)):
            for j in range (i+1, len(n)):
                pos = -1 * (n[i] + n[j])
                if pos in P:
                    # INCORRECT:
                    # TypeError: un-hashable type: 'set'
                    # as sets are mutable
                    # instead do
                    # tuple(sorted([p[i], p[j], neg]))
                    # as tuples are not mutable, and thus hashable
                    res.add(set(sorted([n[i], n[j], pos])))

        # (a, b, -c)
        for i in range(len(p)):
            for j in range(i+1, len(p)):
                neg = -1 * (p[i] + p[j])
                if neg in N:
                    # INCORRECT:
                    # TypeError: un-hashable type: 'set'
                    # as sets are mutable
                    # instead do
                    # tuple(sorted([p[i], p[j], neg]))
                    # as tuples are not mutable, and thus hashable
                    res.add(set(sorted([p[i], p[j], neg])))

        return list(res)

Find the Bug: Did not increment pointers if res == 0 case

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        res = set()
        n = len(nums)
        nums.sort()

        for i in range(n - 2):


            # only iterate over 1 number once
            if i > 0 and nums[i] == nums[i-1]:
                continue

            # only allow negative numbers
            if nums[i] > 0:
                break


            left, right = i + 1, n-1

            # '<' becuase left != right
            while left < right:
                currSum = nums[i] + nums[left] + nums[right]

                if currSum == 0:
                    
                    res.add((nums[i], nums[left], nums[right]))
                
                    # INCORRECT:
                    # forgot to iterate both left and right
                    # should have been:
                    # left += 1
                    # right -= 1

                elif currSum < 0:
                    left += 1
                else:
                    right -= 1
            
        return res

Solution 1: Mimicking Two Sum by doing Per Element Opposite Ends Pointer Shift by BinarySearch Modification for 0 (Sorting) - Two Pointers/K Pointer Variants

    def threeSum(self, nums: List[int]) -> List[List[int]]:

        # Note: Two Sum vs 3Sum
        # Two sum, finding two numbers whose sum equals a target is simple
        # with hashmaps or two pointer solutions being efficient
        # 3Sum adds complexity with a third variable,
        # but converting 3Sum into a two sum problem allows
        # the use of hashmap or two pointer solutions again

        # set ensures no duplicate triplets
        # space complexity: 
        results = set()
        n = len(nums)

        # time complexity: default python sorting TimSort, O(n log n)
        nums.sort()

        # mimic 
        # time complexity
        for i in range(n - 2):

            # skip iteration:
            # i should only "BinarySearch" through any number once 
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # early break: 
            # only allow negative numbers for i in (i, j, k)
            if nums[i] > 0:
                break

            # Set up "BinarySearch" modification:          
            # set new left boundary for iteration BinarySearch
            # reset right boundary for iteration BinarySearch  
            left, right = i + 1, n - 1

            # "BinarySearch" modification: 
            # "<": working within subarray separate from i
            # cannot evaluate num at left == right given constraint i != j, i != k, j != k
            # Base case: no more array remaining to search
            # complement for numbers[i] was not found, 
            # continue iteration for i
            # time complexity: BinarySearch on subarray of n elements O(log n) for n iterations, leading to O(n log n)
            while left < right:
                
                # grab current sum (i, j, k)
                currSum = nums[i] + nums[left] + nums[right]

                # found target sum
                if currSum == 0:
                    
                    # add triplet to result set
                    results.add((nums[i], nums[left], nums[right]))

                    # skip iteration:
                    # j and k should only "BinarySearch" through any number once 
                    left += 1
                    right -= 1

                    # skip iteration:
                    # j and k should only "BinarySearch" through any number once 
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

                # "BinarySearch" on relevant subsection
                # update left or right pointer
                elif currSum < 0:
                    left += 1
                else:
                    right -= 1

        # convert valid set of tuple triplets into valid list of tuple triplets

        # Time Complexity: O(n^2)
        # Space Complexity: O(n)
        return list(results)

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Sorting	O(n log n)	O(1)	Sorting array using TimSort in O(n log n)	No additional memory allocation for in place sorting
Outer Loop	O(n)	O(1)	Iterate over n elements O(n)	No additional memory allocation for iteration constant O(1)
Inner Loop	O(n²)	O(1)	Two pointer traversal for subarray search over n elements O(n) per outer iteration n O(n), leading to O(n²)	No additional memory allocation for pointer traversal
Result Storage	O(1)	O(n)	Insert takes constant O(1)	Stores k unique triplets O(k) which in worst case is just O(n)
Overall	O(n²)	O(n)	Two pointer traversal for n elements dominates, leading to O(n²)	Worst case of n/3 valid triplets O(n/3), which leads to O(n)

Solution 2: Grouping By Parity 4 Triplet Combinations (time limit exceeded) - Two Pointers/Algorithm

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        # Note: Two Sum vs 3Sum
        # Two sum, finding two numbers whose sum equals a target is simple
        # with hashmaps or two pointer approaches being efficient
        # 3Sum adds complexity with a third variable.
        # Grouping techniques aim to narrow and organize the solution space
        # reducing redundant checks while finding valid triplets

        # positive, negative, and zero sets
        # space complexity: 
        p, n, z = [], [], []
        
        # set ensures no duplicate triplets
        # space complexity: 
        res = set()

        # time complexity: iterate over list of n length O(n)
        for i in nums:
            if i < 0:
                n.append(i)
            elif i > 0:
                p.append(i)
            else:
                z.append(i)

        # sets for unique groups
        # time complexity: convert list into set O(n)
        P, N = set(p), set(n)

        # (0, num, -num)
        # time complexity: iterate over positive numbers list n length O(n)
        if len(z) > 0:
            for i in P:                
                # time complexity: negative target lookup in constant O(1)
                nTarget = -i
                if nTarget in N:
                    res.add((nTarget, 0, i ))

        # (0, 0, 0)
        # time complexity: len operation constant O(1)
        if len(z) >= 3:
            res.add((0, 0, 0))

        # (-, -, +) negative pairs
        # time complexity: iterate over list of negative numbers n length O(n)
        for i in range(len(n)):
            # time complexity: iterate over list of negative numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(n)):
                # time complexity: lookup operation constant O(1)
                pTarget = -(n[i] + n[j])
                if pTarget in P:
                    res.add(tuple(sorted([n[i], n[j], pTarget])))
        
        # (-, +, +) positive pairs
        # time complexity: iterate over list of positive numbers n length O(n)
        for i in range(len(p)):
            # time complexity: iterate over list of positive numbers n length O(n) per outer iteration O(n), leading to O(n^2)
            for j in range(i+1, len(p)):
                # time complexity: lookup operation constant O(1)
                nTarget = -(p[i] + p[j])
                if nTarget in n:
                    res.add(tuple(sorted([p[i], p[j], nTarget])))

        # convert valid set of tuple triplets into valid list of tuple triplets

        # overall: time complexity O(n^2) 
        # overall: space complexity O(n)
        return list(res)

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Grouping Iteration	O(n)	O(n)	Iterate over list of n length to group into positive, negative, and zero lists O(n)	Grouping list of n length into three groups O(n)
Conversion to Sets	O(n)	O(n)	Convert list of positive and negative numbers into sets O(n)	Convert list of n length O(n)
Inverse Check	O(n)	O(1)	Iterate over positive list n length O(n) and lookup inverse in negative set O(1), leading to O(n)	No additional memory allocation for iteration O(1)
Zero Check	O(1)	O(1)	Zero list len check in constant O(1)	No additional memory allocation for len check O(1)
Negative Pairs	O(n²)	O(n)	Outer/Inner iteration over list of negative numbers O(n²) with inverse positive lookup O(1), leading to O(n²)	Adding n/3 triplets to result O(n/3), leading to O(n)
Positive Pairs	O(n²)	O(n)	Outer/Inner iteration over list of positive numbers O(n²) with inverse positive lookup O(1), leading to O(n²)	Adding n/3 triplets to result O(n/3), leading to O(n)
Overall	O(n²)	O(n)	Negative and positive iterations dominate leading to O(n²)	Memory allocation for n/3 valid triplets, leading to O(n)

11. Container With Most Water ::1:: - Medium

Topics: Array, Two Pointers, Greedy

Intro

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store

nums	Output
[1,8,6,2,5,4,8,3,7]	49
[1,1]	1

Constraints:

trapped water involves the space between and including two walls (bars). width = (right - left)

Abstract

We need to calculate the container with the most water.

The integer value represents the height of a side of a container, and the distance between two sides is calculated using the index of the array

We can iterate over the array calculating the sides of the container that will give us the most water.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark
Brute Force
Two Pointer Early Break

Brute Force

    def maxArea(self, height: List[int]) -> int:

        n = len(height)
        maxWater = 0
        
        # time complexity: iterate over array of n length O(n)
        for i in range(n - 1):

            # time complexity: iterate over array of n length for each outer iteration O(n^2)
            for j in range(i + 1, n):

                # calculate current water
                currWater = min(height[i], height[j]) * (j - i)
                maxWater = max(maxWater, currWater)
        
        # overall: time complexity O(n^2)
        # overall: space complexity O(1)
        return maxWater

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Outer loop	O(n)	O(1)	Iteration over list of n length O(n)	No additional memory allocation for iteration O(1)
Inner loop	O(n²)	O(1)	Iteration over list of n length per iteration in outer loop O(n²)	No additional memory allocation for iteration O(1)
Curr Water	O(1)	O(1)	Water height operation takes constant O(1)	No additional memory allocation O(1)
Overall	O(n²)	O(1)	Inner loop dominates leading to O(n²)	No additional memory allocation leading to O(1)

Solution 1: Greedy Opposite Ends Pointer Shift by BinarySearch Modification - Two Pointers/Opposite Ends

    def maxArea(self, height: List[int]) -> int:
        
        # set up "BinarySearch" modification
        left, right = 0, len(height)-1
        maxWater = 0 

        # time complexity: two pointer iteration over list of n length O(n)
        while left < right:

            # grab smaller height between outside pointers
            smallerHeight = min(height[left], height[right])

            # width includes walls: 
            # [1, 1] is 1 water, so (rightIndex - leftIndex) = width
            # calculate curr water between outside pointers, (smallerHeight * width)
            currWater = smallerHeight * (right-left)
            
            # compare to global max
            maxWater = max(maxWater, currWater)

            # Greedy:
            # As we move pointers inwards, width is guaranteed to get shrink
            # Thus, we can continue to move our pointers,
            # until we hit a bigger height than our current smaller height
            # time complexity: two pointer iteration over list of n length O(n)
            if height[left] < height[right]:
                # step past current left/right wall combination
                left += 1
                # Greedy:
                while left < right and height[left] < smallerHeight:
                    left += 1 
            else:
                # step past current left/right wall combination
                right -= 1
                # Greedy:
                while left < right and height[right] < smallerHeight:
                    right -= 1

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return maxWater

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Iteration	O(n)	O(1)	Iteration over list of n length with two pointers O(n)	No additional memory allocation for iteration O(1)
Curr Water	O(1)	O(1)	Water height operation takes constant O(1)	No additional memory allocation O(1)
Overall	O(n)	O(1)	Iteration over list of n length dominates leading to O(n)	No additional memory allocation O(1)

42. Trapping Rain Water ::3:: - Hard

Topics: Array, Two Pointers, Dynamic Programming, Stack, Monotonic Stack

Intro

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

height	Output
[0,1,0,2,1,0,1,3,2,1,2,1]	6
[4,2,0,3,2,5]	9

Constraints:

trapped water involves the space between two walls (bars). width = (right - left - 1)

Abstraction

To calculate trapped water:

[1, 0, 1] -> 1 unit of water

[1, 0, 2] -> 1 unit of water

[1, 0, 0] -> 0 units of water

Definition of trapped water is: [ min(left, right) - currHeight ]

Now we need a way to traverse the array that allows us to take advantage of this pattern.

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark
Brute Force
Two Pointer Early Break

Brute Force

    def trap(self, height: List[int]) -> int:
        n = len(height)
        water = 0

        # time complexity: iterate over list of n length o(n)
        for i in range(n):

            # Use two pointers to calculate leftMax and rightMax
            leftMax, left = 0, i
            rightMax, right = 0, i

            # time complexity: iterate over left hand side of list n length per outer iteration O(n^2)
            while left >= 0:
                leftMax = max(leftMax, height[left])
                left -= 1

            # time complexity: iterate over right hand side of list n length per outer iteration O(n^2)
            while right < n:
                rightMax = max(rightMax, height[right])
                right += 1

            # curr water trapped for curr bar i
            water += min(leftMax, rightMax) - height[i]

        # overall: time complexity O(n^2)
        # overall: space complexity O(1)
        return water

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Iterate
Left/Right max
Curr Water
Overall

Find the Bug: Complete misunderstanding of water heights (haha)

    def trap(self, height: List[int]) -> int:
        
        # dynamic programming
        n = len(height)

        leftMax = [0] * n
        rightMax = [0] * n
        water = 0

        # INCORRECT:
        # what are you deranged?!?!?
        # why do you need a separate max!
        # its just the previous max vs the current height
        left = 0
        for i in range(1, n):
            left = max(left, height[i-1])
            leftMax[i] = left

        # INCORRECT:
        # again! only a deranged person would create a separate 
        # max variable to compare against a max array
        right = 0
        for i in range(n-2, -1, -1):
            right = max(right, height[i+1])
            rightMax[i] = right

        for i in range(n):
            water += min(rightMax[i], leftMax[i]) - height[i]

        return water

Find the Bug: Two Pointers Early Break

    def trap(self, height: List[int]) -> int:
        
        L, R = 0, len(height) - 1
        water = 0

        # setting curr left/right max to ends of list
        leftMax, rightMax = height[L], height[R]

        # time complexity: iterate over list of n length with two pointers O(n)
        while L < R:
            
            # grabbing weak link
            if height[L] < height[R]:
                # INCORRECT: skips water trapped at previous position before the pointer moved
                L += 1

                # INCORRECT: updating leftMax *before* calculating trapped water causes error
                leftMax = max(leftMax, height[L])

                # INCORRECT: water calculation uses updated leftMax prematurely
                water += min(leftMax, rightMax) - height[L]

            # grabbing weak link
            else: 
                # INCORRECT: skips water trapped at previous position before the pointer moved
                R -= 1

                # INCORRECT: updating rightMax *before* calculating trapper water causes error
                rightMax = max(rightMax, height[R])

                # INCORRECT: water calculation uses updated rightMax prematurely
                water += min(leftMax, rightMax) - height[R]
        
        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return water

Find the Bug: Not checking if left wall exists after pop

    def trap(self, height: List[int]) -> int:

        stack = []  
        water = 0

        for i in range(len(height)):

            while stack and height[i] > height[stack[-1]]:

                depthCandidateIndex = stack.pop() 

                # INCORRECT:
                # we are assuming a left wall exists,
                # when the stack might just be 1 element which we just popped
                # so it could be empty
                # missing:
                # if not stack:
                #   break 

                rightWallIndex = i
                leftWallIndex = stack[-1]
                distance = rightWallIndex - leftWallIndex - 1

                rightHeight = height[rightWallIndex]
                depthHeight = height[depthCandidateIndex]
                leftHeight = height[leftWallIndex]

                boundedHeight = min(rightHeight, leftHeight) - depthHeight
                water += distance * boundedHeight

            stack.append(i)

        return water

Find the Bug: Overwriting variables accidentally

    def trap(self, height: List[int]) -> int:
        stack = []  
        water = 0

        for i in range(len(height)):

            while stack and height[i] > height[stack[-1]]:

                depthCandidate = stack.pop() 

                if not stack:
                    break

                leftIndex = stack[-1]
                rightIndex = i
                distance = rightIndex - leftIndex - 1

                leftHeight = height[leftIndex]
                rightHeight = height[rightIndex]
                depthHeight = height[depthCandidate]

                # INCORRECT:
                # TypeError: 'int' object is not subscriptable
                # because are overwriting 'height'
                # instead use boundedHeight 
                height = min(leftHeight, rightHeight) - depthHeight

                water += distance * height
            
            stack.append(i)

        return water

Find the Bug: Bad For Loop syntax

    def trap(self, height: List[int]) -> int:
        
        n = len(height)
        water = 0
        
        leftMax = [0] * n
        rightMax = [0] * n

        leftMax[0] = height[0]
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])
        
        rightMax[n - 1] = height[n - 1]
        # INCORRECT:
        # missing ',' between -1
        # for loop says to go till -2
        # for loop says: for i in range(n - 2, -2)
        for i in range(n - 2, -1 -1):
            rightMax[i] = max(rightMax[i + 1], height[i])

        for i in range(n):
            water += min(rightMax[i], leftMax[i]) - height[i]

        return water

Solution 1: Monotonic Traversal 2 Outer/2 Inner Pointers Creating Bounds Opposite Ends Pointer Shift by BinarySearch Modification (Sorting) - Two Pointers/K Pointer Variants

    def trap(self, height: List[int]) -> int:

        # Note: 
        # Outer Pointers: act as wall/side to bound inner pointers
        # Inner Pointers: traverse inward from both ends to track height for current position
        # Water Trapping: compare inner pointer to outer pointers wall/side to determine 
        # if theres enough depth to trap water

        # Set up "BinarySearch" modification
        # outer pointers
        outerLeftMax, outerRightMax = 0, 0
        # inner pointers
        left, right = 0, len(height) - 1
        water = 0

        # Monotonic "BinarySearch" modification
        # time complexity: two pointer iteration over list of n length O(n)
        while left < right:

            # Monotonic "BinarySearch" on relevant subsection
            # implies: height[left] < height[right]
            # case 1: [5, 0, 3, 2, 4, 6], left < right for entire array 
            # case 2: [5, 0, 3, 9, 4, 6], left < right broken at some point
            # case 1 implies: while height[left] < height[right] 
            # and while height[left] < outerLeftMax
            # then: water is limited by outerLeft/outerRight 
            # as water will eventually be caught by right
            if height[left] < height[right]:

                # case 1: implication broken
                # implies: outerLeftMax < height[left] < height[right] 
                # then: update outerLeftMax             
                if height[left] >= outerLeftMax:
                    outerLeftMax = height[left]

                # case 1: implication applies
                # implies: height[left] < outerLeftMax < height[right]
                else:
                    water += outerLeftMax - height[left]

                # shift pointer
                left += 1

            # implies: height[right] < height[left]
            else:
                
                # case 1: implication broken
                # implies: outerRightMax < height[right] < height[left]     
                # then: update outerRightMax
                if height[right] >= outerRightMax:
                    outerRightMax = height[right]

                # case 1: implication applies
                # implies: height[right] < outerRightMax < height[left]
                else:
                    water += outerRightMax - height[right]

                # shift pointer
                right -= 1

        # overall: time complexity O(n)
        # overall: space complexity O(1)
        return water

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Iteration	O(n)	O(1)	Two pointer iteration over list of n length O(n)	No additional memory allocation required for iteration O(1)
Comparing Heights	O(1)	O(1)	Height lookup and comparison in constant O(1)	No additional memory allocation for lookup or comparison O(1)
Water Calculation	O(1)	O(1)	Water calculation and sum in constant O(1)	No additional memory allocation for water calculation or sum O(1)
Overall	O(n)	O(1)	Two pointer iteration over list of n length dominates, leading to O(n)	No additional memory allocation required, leading to O(1)

Solution 2: Monotonic Stack - Two Pointers/Algorithm

    def trap(self, height: List[int]) -> int:

        # Note: 
        # Monotonic Stack: A stack that maintains monotonic decreasing heights 
        # When monotonic decreasing rule breaks, curr height will serve as right wall,
        # and if stack is non empty, top of stack will serve as depth, 
        # and top of stack - 1 will serve as left wall

        # Monotonic stack to store indices
        stack = []  
        water = 0

        # push and pop each bar at most once
        # time complexity: iterate over list of n length O(n)
        for i in range(len(height)):

            # Check: stack is non empty, depth candidate exists
            # Check: if current height[i] breaks monotonic decreasing order,
            # will be viable to act as a right wall
            # implies: we keep appending while monotonic decreasing stays valid
            # implies: stack is kept in monotonic decreasing order
            # implies: when monotonic decreasing breaks, we have found right wall
            while stack and height[i] > height[stack[-1]]:
                
                # curr while loop iteration:
                # height[i]: right wall
                # pop stack[-1]: depth candidate
                # peak stack[-2]: left wall

                # while stack is non-empty:
                # stack.pop() will iterate depth candidate and left wall
                # essentially dragging the right wall over the monotonic stack, 
                # adding all possible water, with all combinations of left wall and depth candidate
                # until a depth candidate is taller than the current right wall
                # then we just add the right wall to the stack maintaining monotonic order
                depthCandidateIndex = stack.pop() 

                # Check: if stack empty after pop, no left wall exists
                # implies: cannot trap water, end while loop, add item to stack
                if not stack:
                    break

                # trapped water involves the space between two walls, excluding walls
                # width = (right - left - 1)

                # After stack.pop():
                # height[i]: right wall
                # popped depthCandidate: depth
                # peak stack[-1]: left wall
                # while loop check implies: depthCandidate < height[i]
                # monotonic stack check implies: depthCandidate < stack[-1]
                rightWallIndex = i
                leftWallIndex = stack[-1]
                distance = rightWallIndex - leftWallIndex - 1

                rightHeight = height[rightWallIndex]
                depthHeight = height[depthCandidateIndex]
                leftHeight = height[leftWallIndex]

                # subtract the depth minus smaller height to get water depth
                boundedHeight = min(rightHeight, leftHeight) - depthHeight

                # add the trapped water for the current segment 
                # [5, 0, 0, 2]
                # in this case, (0, 0, 2)
                # would return with the left wall being 0
                # so no water captured
                # but then, (5, 0, 2)
                # would return with the right wall being 5
                # in which case we would need the distance.
                
                # so distance will always be 1
                # unless we have a run of identical heights
                water += distance * boundedHeight

            # implies: monotonic decreasing is still valid
            # implies: append height to stack
            stack.append(i)

        # overall: time complexity O(n)
        # overall: space complexity O(n) (due to the stack)
        return water

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
Iteration	O(n)	O(1)	Iterate over list of n length O(n)	No additional memory allocation for iteration O(1)
Stack Operations	O(n)	O(n)	Each push() and pop() operation in constant O(1) but for n elements leading to O(1) * n, leading to O(n)	Stack holding n elements O(n)
Heights comparisons	O(1)	O(1)	Each comparison in while loop in constant O(1)	No additional memory allocation for comparison O(1)
Water Calculation	O(1)	O(1)	Calculating distance and bounded height in constant O(1)	No additional memory for distant or bounded height operations O(1)
Overall	O(n)	O(n)	Iterating over list of n length dominates, leading to O(n)	Stack growing for n elements dominates, leading to O(n)

Solution 3: Dynamic Programming - Two Pointers/Algorithm

    def trap(self, height: List[int]) -> int:
        
        # Note:
        # Dynamic Programming Concept:
        # Left Maximum Array: Stores the maximum height encountered from the start up to each index i.
        # Right Maximum Array: Stores the maximum height encountered from the end up to each index i.
        # Avoid recomputing maximum heights repeatedly.

        n = len(height)
        if n == 0:
            return 0

        # Arrays to store max heights from the left and right
        # leftMax[i]: Maximum height from 0 to index i
        # rightMax[i]: Maximum height from index i to (n-1)
        leftMax = [0] * n
        rightMax = [0] * n
        water = 0

        # calculate left max for each bar
        # compare previous max, with current bar height,
        # as curr may be new max, for the curr index
        # time complexity: iterate over list of n length O(n)
        leftMax[0] = height[0]
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])

        # calculate right max for each bar
        # compare previous max, with current bar height,
        # as curr may be new max, for the curr index
        # time complexity: iterate over list of n length O(n)
        rightMax[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])

        # calculate trapped water for each bar
        # time complexity: iterate over list of n length O(n)
        for i in range(n):

            # The water trapped above bar i is determined by the minimum between
            # leftMax[i] and rightMax[i] minus the curr bar height
            water += min(leftMax[i], rightMax[i]) - height[i]

        # overall: time complexity O(n)
        # overall: space complexity O(n)
        return water

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
LeftMax Calculation	O(n)	O(1)	Iterate over height list of n length O(n)	Stores max height for current index for list of n length O(n)
RightMax Calculation	O(n)	O(n)	Iterate over height list of n length O(n)	Store max height for current index for list of n length O(n)
Water Calculation	O(n)	o(1)	Iterate over max height list of n length O(n)	No additional memory allocation for water calculation O(n)
Overall	O(n)	O(n)	Iterating over height list dominates, leading to O(n)	Memory allocation for leftMax and rightMax arrays dominates, leading to O(n)

LeetCode: Two Pointers