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: Reverse Slicing [::-1] Comparison [TC Opt] - Two Pointers/Algorithm

    def isPalindrome(self, s: str) -> bool:
        
        # Note:
        # Appending to a list and joining once is more efficient than repeatedly
        # appending to a string. Strings are immutable, so each concatenation
        # creates a new string and copies all existing characters.
        # tc: list append + join: O(m), repeated string concat: O(m^2)

        # sc: cleaned version of string O(n)
        cleaned = []

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

            # only grab alphaNum chars
            if c.isalnum():
                cleaned.append(c.lower())
        
        # tc: join alphaNum list O(n)
        phrase = "".join(cleaned)

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

        # tc: single iteration over the two strings
        # sc: creates new reversed string
        res = phrase == phrase[::-1]

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

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks
cleaned 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: Cleaned String Opposite Ends [TC Opt] - 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')

        # Note:
        # Ascii Table Unicode Value: A = 65, a = 97, difference of 32

        # 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 [SC Opt] - 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: skip non-alphaNum, 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: compare alphaNum
            if leftChar != rightChar:
                return False

            # Left/Right: shrink L/R 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 2 Catchup pointers [TC Opt] - Two Pointers/Catchup

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

        # Note:
        # Appending to a list and joining once is more efficient than repeatedly
        # appending to a string. Strings are immutable, so each concatenation
        # creates a new string and copies all existing characters.
        # tc: list append + join: O(m), repeated string concat: O(m^2)

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

        # tc: iterate list O(n)
        for s in strs:
            
            # Note:
            # custom delimiter to mark start of string "{length}#" -> "5#""

            # tc: delimiter length proportional to log10(m) ~= O(1)
            lenDelim = str(len(s)) + "#"
            left = 0
            while left < len(lenDelim):
                encoded.append(lenDelim[left])
                left += 1
            
            # tc: iterate string O(m)
            left = 0
            while left < len(s):
            
                # append each char
                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):

            # set right to start of length prefix
            right = left

            # tc: log 10 (m) ~= O(1)
            # shift right 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])
           
            # set left to start of next custom delimiter
            left = right + length
            
            # after:
            # [ 2 # h i 3 # b y e ...]
            # [ 0 1 2 3 4 5 6 7 8 ...]
            #       ^   ^
            #       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 [TC Opt] - Two Pointers/One Pointer with Auxiliary State

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

        # Note:
        # Appending to a list and joining once is more efficient than repeatedly
        # appending to a string. Strings are immutable, so each concatenation
        # creates a new string and copies all existing characters.
        # tc: list append + join: O(m), repeated string concat: O(m^2)

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

        # tc: 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

            # tc: 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: tc O(n^2)
        # overall: sc O(n^2)
        return ''.join(encoded)


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

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

        # tc: 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  

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

            # tc: iterate string O(n) for n delimiters O(n), O(n^2)
            substring = []
            for _ in range(currLen):

                # grab string of currLen
                substring.append(encoded[left])
                left += 1
            
            # left is set to start of next length

            # after:
            # [ 2 # h i 3 # b y e ...]
            # [ 0 1 2 3 4 5 6 7 8 ...]
            #           ^
            #           l

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


        # overall: tc O(n^2)
        # overall: sc 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 [Slow TC] - Two Pointers/One Pointer with Auxiliary State

    def twoSumII(self, numbers: List[int], target: int) -> List[int]:
        
        # tc: iterate list O(n)
        for i in range(len(numbers)): 

            # search for complement
            currComplementSearch = target - numbers[i]
            
            # update boundaries
            # tc: binarySearch O(log n) for n numbers O(n), O(n log n)
            left, right = i + 1, len(numbers) - 1
            
            # Note:
            # BinarySearch Pattern (1)
            # 3 Paths: Check Middle Target, If Left Path, Else Right Path

            # base case: no more array to search, numbers[i] complement not found, next iteration
            while left <= right:
                
                # grab middle element
                midIndex = (left + right) // 2
                midNum = numbers[midIndex]

                # check middle target: found sum
                if midNum == currComplementSearch:

                    # convert to 1-indexed array, per test cases
                    return [i + 1, midIndex + 1]  

                # if left path: currSum is too low
                elif midNum < currComplementSearch:
                    left = midIndex + 1

                # else right path: currSum is too high
                else:
                    right = midIndex - 1

        # overall: tc O(n log n)
        # overall: sc 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 [TC Opt] - 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]  

            # Note:
            # BinarySearch Pattern (1)
            # 3 Paths: check middle target, if left path, else right path

            # check middle target: found sum
            if currSum == target:
                
                # convert to 1-indexed array, per test cases
                return [left + 1, right + 1]

            # eheck left path: currSum is too low
            elif currSum < target:
                left += 1

            # else right path: currSum is too high
            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: [Sorting] Two Sum Mimic By Per Element Opposite Ends Pointer Shift By BinarySearch Modification For 0 [TC Opt] - Two Pointers/K Pointer Variants

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

        # Note:
        # 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 adding constraints turns 3Sum into a two sum
        # and allows the use of hashmap or two pointer solutions again

        # set ensures no duplicate triplets
        # sc: relative to input O(n)
        results = set()
        n = len(nums)

        # tc: python (2.3-3.10) TimSort, Python (3.11+) PowerSort Worst/Avg: O(n log n), Best: O(n)
        # sc: sorts in place, no extra memory O(1)
        nums.sort()

        # tc: iterate over list O(n)
        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

            # Note:
            # BinarySearch Pattern (1)
            # 3 Paths: check middle target, if left path, else right path

            # shift left boundary
            # reset right boundary to rightmost  
            left, right = i + 1, n - 1

            # BinarySearch Modification (1)
            # cannot evaluate num at left == right given constraint i != j, i != k, j != k
            # thus, change to left < right instead of left <= right

            # Base case: no more array remaining, numbers[i] complement not found,
            # next iteration
            
            # tc: BinarySearch on n elements O(log n), for n iterations O(n), (n log n)
            while left < right:
                
                # grab current sum (i, j, k)
                currSum = nums[i] + nums[left] + nums[right]
                
                # check middle target: found sum
                if currSum == 0:
                    
                    # add triplet to result set
                    results.add((nums[i], nums[left], nums[right]))

                    # complete pair skip:
                    # only j and k can add to 0, we can step to next pair 
                    left += 1
                    right -= 1

                    # Early duplicates skip:
                    # we already checked the combination of j and k, we can skip all duplicates
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1

                # if left path: currSum is too low 
                elif currSum < 0:
                    left += 1
                
                # else right path: currSum is too low
                else:
                    right -= 1

        # convert set of tuple triplets into list

        # 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: [No Sorting] Grouping By Parity 4 Triplet Combinations [Time Limit Exceeded] - Two Pointers/Algorithm

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

        # group by parity: positive, negative, and zero sets
        # sc: relative to input O(n)
        p, n, z = [], [], []
        
        # set ensures no duplicate triplets
        # sc: relative to input O(n)
        res = set()

        # tc: iterate 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 ensures no duplicates
        # tc: convert list into set O(n)
        P, N = set(p), set(n)

        # (0, 0, 0): at least 3 0's for a valid triplet
        # tc: len operation constant O(1)
        if len(z) >= 3:
            res.add((0, 0, 0))

        # (0, +, -): at least 1 additive inverse for a valid triplet with at least 1 0
        if len(z) > 0:
            # tc: iterate n positive numbers O(n)
            for i in P:                
                nTarget = -i
                # tc: inverse lookup constant O(1)
                if nTarget in N:
                    # tc: put constant O(1)
                    res.add((nTarget, 0, i))

        # (-, -, +): negative pairs which are additive inverse of 1 positive number
        # tc: iterate n negative numbers O(n)
        for i in range(len(n)):
            # tc: iterate n O(n)
            for j in range(i+1, len(n)):
                pTarget = -(n[i] + n[j])
                # tc: inverse lookup constant O(1)
                if pTarget in P:
                    # tc: put constant O(1)
                    res.add(tuple(sorted([n[i], n[j], pTarget])))
        
        # (-, +, +): positive pairs which are additive inverse of 1 negative number
        # tc: iterate n positive numbers O(n)
        for i in range(len(p)):
            # tc: iterate n positive numbers O(n)
            for j in range(i+1, len(p)):
                nTarget = -(p[i] + p[j])
                # tc: inverse lookup constant O(1)
                if nTarget in N:
                    # tc: put constant O(1)
                    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 With Greedy Shift by BinarySearch Modification [TC Opt] - Two Pointers/Opposite Ends

    def maxArea(self, height: List[int]) -> int:
        
        # boundaries
        left, right = 0, len(height)-1
        maxWater = 0 

        # tc: iteration n O(n)
        while left < right:

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

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

            # Greedy Shift:
            # As we move pointers inwards, width is guaranteed to shrink
            # Thus, the only way to beat our currWater is with a taller height
            # Thus, we can continue to move our pointers,
            # until we hit a bigger height than our current smaller height
            # Or conversely, we only need to stop and check at a bigger height

            # tc: iteration n list O(n)
            if height[left] < height[right]:
                # step past current left/right wall combination
                left += 1
                # Greedy Shift:
                while left < right and height[left] < smallerHeight:
                    left += 1 
            else:
                # step past current left/right wall combination
                right -= 1
                # Greedy Shift:
                while left < right and height[right] < smallerHeight:
                    right -= 1

        # overall: tc O(n)
        # overall: sc 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 L/R Pointers] 2 Inner/Outer Pointers Traversal Creating Bound Buckets By Monotonic Opposite Ends Pointer Shift Modification - Two Pointers/K Pointer Variants

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

        # Bound Buckets:
        # [4, 0, 2, 6, 3, 5]: Monotonic quality defines buckets 
        #                      1. Bucket from index 0-3 with heights of [4, 0, 2, 6]   (left to right monotonic increasing bucket)
        #                      2. Bucket from index 3-5 with heights of [6, 3, 5]      (left to right monotonic decreasing bucket)
        #
        #    When we use 4 and 6 as the left and right bucket walls, the bucket will catch any water up to and including 4
        #    When we use 6 and 5 as the left and right bucket walls, the bucket will catch any water up to and including 5

        #   Bucket 1: w     Bucket 2: m
        #       --------- ++++++
        #                *     
        #                *  m  *
        #       *  w  w  *  m  *
        #       *  w  w  *  *  *
        #       *  w  *  *  *  *
        #       *  w  *  *  *  *
        #      ------------------
        #       0  1  2  3  4  5

        # Types Of Graphs
        # case 1: [4, 0, 2, 1, 3, 5], left < right for entire array (bucket from 5 -> 6)
        # case 2: [4, 0, 2, 6, 3, 5], left < right broken at some point (bucket from 5 -> 9, 9 -> 6)

        #    case 1:                     case 2:
        #        -------------              --------- ++++++
        #                                            *     
        #                      *                     *  m  *
        #       *  w  w  w  w  *            *  w  w  *  m  *
        #       *  w  w  w  *  *            *  w  w  *  *  *
        #       *  w  *  w  *  *            *  w  *  *  *  *
        #       *  w  *  *  *  *            *  w  *  *  *  *
        #      ------------------          ------------------
        #       0  1  2  3  4  5            0  1  2  3  4  5
        #       ^              ^            ^              ^
        #       L              R            L              R

        # Creating Buckets: 
        # L/R Outer Pointers: serve as left and right most wall for buckets
        # L/R Inner Pointers: traverse inward from both ends to determine if monotonic quality (bucket definition) as broken
        # Water Trapping: using implications to know if left or right most wall for buckets determines water height

        # Defining Bucket Depth Via Height Implications:
        # case 1 implies: 
        #   1. while height[left] < height[right] 
        #   2. and while height[left] < outerLeftMax
        #   3. we also know that height[right] < outerRightMax (same implication as 2. but for the right)
        #   then (eventually), there is a bucket from [outerLeftMax ... left ... outerRightMax]

        # outer pointers
        outerLeftMax, outerRightMax = 0, 0
        
        # inner pointers
        left, right = 0, len(height) - 1
        
        water = 0

        # tc: iterate over n O(n)
        while left < right:
            
            # We grab the lower height, so we know that at minimum, this height is bounded by the taller height

            
            # Check: Left wall is shorter than Right wall
            # Implies: Left wall is covered by Right wall
            if height[left] < height[right]:    
                #                   *   
                #                   *   
                #             *     *   
                #       ?     *     *   
                #      ------------------
                #      LM     L     R   

                # Check: Left wall is taller than Left Max
                # Implies: new tallest left wall found
                # Then: Update     
                if height[left] >= outerLeftMax:
                    #                   *   
                    #                   *   
                    #             *     *   
                    #       *     *     *   
                    #      ------------------
                    #      LM     L     R   
                    outerLeftMax = height[left]

                # Check: Left wall is shorter than left max
                # Implies: Left wall is covered by left max
                # Invariant: Left wall is already covered by Right Wall
                # Implies: Left max is also lower than Right Wall
                # Implies: Left max is limiting factor for this bucket
                # Then: Water depth is just limiting factor - height = outerLeftMax - height[left]
                else:

                    #                   *   
                    #       *     w     *   
                    #       *     *     *   
                    #       *     *     *   
                    #      ----------------
                    #      LM     L     R   
                    water += outerLeftMax - height[left]

                # shift pointer
                left += 1

            # Check: Right wall is shorter than Left wall
            # Implies: Right wall is covered by Left Wall
            else:
                #       *              
                #       *                
                #       *     *         
                #       *     *     ?   
                #      ----------------
                #       L     R     RM   

                # Check: Right wall is taller than Right Max
                # Implies: New tallest right wall found
                # Then: update
                if height[right] >= outerRightMax:
                    #       *              
                    #       *                
                    #       *     *         
                    #       *     *     *   
                    #      ----------------
                    #       L     R     RM   
                    outerRightMax = height[right]

                # Check: Right wall is shorter than Right Max
                # Implies: Right Wall is covered by Right Max
                # Invariant: Right Wall is already covered by Left Wall
                # Implies: Right Max is also lower than Left Wall
                # Implies: Right Max is the limiting factor for this bucket
                # Then: Water depth is just limiting factor - height = outerRightMax - height[right]
                else:
                    #       *              
                    #       *     w     *     
                    #       *     *     *    
                    #       *     *     *   
                    #      ----------------
                    #       L     R     RM   
                    water += outerRightMax - height[right]

                # shift pointer
                right -= 1

        # overall: tc O(n)
        # overall: sc 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] Dragging Right Wall Height Over The Array And Catching Water With Depth Candidates And Left Wall By Building Monotonic Stack - Two Pointers/Algorithm

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

        # 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 second top of stack - 1 will serve as left wall
        # we then pop off the top of the stack until the monotonic rule comes back into play,
        # or the right wall becomes the new leftmost wall

        # Stack:
        #      *                                  *                    *                 *              *
        #      *                   *              *            *       *         *       *  w   *       *  *
        #      *  *                *              *  *         *       *  *  w   *       *  *   *       *  *
        #      *  *                *              *  *         *       *  *  w   *       *  *   *       *  *
        #      *  *  *             *              *  *  *  w   *       *  *  *   *       *  *   *       *  *
        #      *  *  *  *     +    *       ==>    *  *  *  *   *   =>  *  *  *   *   =>  *  *   *  ==>  *  *
        #     ------------   new  ---  pop off   ------------ ---     --------- ---     ------ ---     ------
        #    older --> newer        left candidates                                                final result

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

        # iterate over list while pushing and popping each bar only once
        # tc: iterate over n O(n)
        for i in range(len(height)):

            # Check: if stack is non empty, depth candidate (still need to check if left wall candidate exists)
            # Check: if current height[i] breaks monotonic decreasing order, its viable 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
            # implies: we have a depth candidate
            while stack and height[stack[-1]] < height[i]:
                
                # curr while loop iteration:
                # height[i]: right wall
                # pop stack[-1]: depth candidate
                # peak stack[-2]: left wall

                # Check if left wall candidate exists:
                # remove depth candidate from stack, check if stack is non-empty
                # If non-empty, we will essentially dragging the right wall over the monotonic stack, 
                # comparing it to all depth candidates, and adding the corresponding water.
                # Continue until a depth candidate is taller than the current right wall,
                # then we just add the right wall to the stack maintaining monotonic order.
                # Or continue until we run out of left wall/depth candidates,
                # then the right wall becomes the new leftmost wall.
                depthCandidateIndex = stack.pop() 

                # Check: if stack empty after pop, no left wall exists (had 1 but not 2 elements)
                # implies: cannot trap water, end while loop, add item to stack
                if not stack:
                    break

                # Left wall exists:
                # Check water between [Left Wall... Depth Candidate ...Dragged Right Wall] 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]
                # Thus the bucket is: [peak stack[-1]... depthCandidate ... height[i]]

                # Distance:
                rightWallIndex = i
                leftWallIndex = stack[-1]
                distance = rightWallIndex - leftWallIndex - 1

                # Bucket Bounded Height:
                rightHeight = height[rightWallIndex]
                leftHeight = height[leftWallIndex]
                bucketLowerHeight = min(rightHeight, leftHeight)

                depthHeight = height[depthCandidateIndex]

                # Water Caught:
                # Smaller bucket wall height - depth = water getting caught
                waterCaught = bucketLowerHeight - depthHeight

                # add the trapped water for the current segment 
                # [5, 0, 0, 2]
                # in this case, (0, 0, 2)
                # left wall = 0, depth = 0, right wall = 2
                # so no water captured
                # but then due to pop, (5, 0, 2)
                # left wall = 5, depth = 0, right wall = 2
                # so water captured based on distance
                
                # Originally: [5, 0, 0, 2]
                #              0  1  2  3
                # So distance is: 3 - 0 - 1 = 2
                
                # So distance will always be 1 in
                # unless we have a run of identical heights such as above
                water += distance * waterCaught

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

        # overall: tc O(n)
        # overall: sc O(n)
        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] Creating Bucket Left Right Boundaries By Dynamic Programming Tracking Max Height Bucket Bounds Encountered L To R and R to L - Two Pointers/Algorithm

    def trap(self, height: List[int]) -> int:
        
        # Dynamic Programming Concept:
        # Left Maximum Array: Stores the maximum height encountered iterating from left to right (bucket left wall)
        # Right Maximum Array: Stores the maximum height encountered iterating from right to left (bucket right wall)
        # Avoid recomputing maximum heights repeatedly, so instead build the bucket walls as you go.

        # Empty Check:
        n = len(height)
        if n == 0:
            return 0

        # Iteration Arrays:
        # Store max heights from perspective of iterating left to right and right to left for all indexes
        # leftMax[i]:  Maximum height from  0 -> i:    (iterating left to right)
        # rightMax[i]: Maximum height from  i <- n-1:  (iterating right to left)
        # sc: relative to input O(n)
        leftMax = [0] * n
        rightMax = [0] * n
        water = 0

        # First Max Left To Right:
        leftMax[0] = height[0]

        # Iterating Left To Right:
        # Compare previous max to current height
        # tc: iterate over n O(n)
        for i in range(1, n):
            previousMax = leftMax[i-1]
            leftMax[i] = max(previousMax, height[i])

        # First Max Right To Left:
        rightMax[n-1] = height[n-1]

        # Iterating Right To Left:
        # Compare previous max to current height
        # tc: iterate over n O(n)
        for i in range(n-2, -1, -1):
            previousMax = rightMax[i+1]
            rightMax[i] = max(previousMax, height[i])

        # Depth Calculation:
        # tc: iterate over n O(n)
        for i in range(n):

            # Bucket Wall Height:
            # The bucket is bounded by lower of 2 maxes (they represent the Left and Right bucket side heights)
            # Just subtract the lower height against the height of the bottom of the bucket
            water += min(leftMax[i], rightMax[i]) - height[i]

        # overall: tc O(n)
        # overall: sc 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