data structures and algorithms
LeetCode: Two Pointers
68 min read
#data structures and algorithmsTable Of Content
Two Pointers Intro
- What are Two Pointers
- Two Pointers Application: One Pointer with Auxiliary State
- Two Pointers Application: Opposite Ends
- Two Pointers Application: Sliding Window
- Two Pointers Application: Fast & Slow Pointers
- Two Pointers Application: Partitioning
- Two Pointers Application: Parallel Pointer Traversal
- Two Pointers Application: Catchup
- Two Pointers Application: K Pointer Variants
- Two Pointers Application: Algorithm
125. Valid Palindrome ::3:: - Easy
- Intro
- Abstraction
- Space & Time Complexity
- Brute Force One Pointer
- Find the Bug: Less than instead of Less than or equal to
- Find the Bug: Not Moving Pointers (thinking we are)
- Find the Bug: Missing Char Palindrome Comparison (again, im half asleep, my bad :) ]
- Solution 1: Slicing Traversing in Reverse Order - Two Pointers/Algorithm
- Solution 2: Pre Clean Opposite Ends Comparison - Two Pointers/Opposite Ends
- Solution 3: In Place Opposite Ends Comparison - Two Pointers/Opposite Ends
271. String Encode and Decode ::2:: - Medium
- Intro
- Abstraction
- Space & Time Complexity
- Find the Bug: Decoded Length + Delimiter (Grabbed str(len) instead int(len))
- Find the Bug: Decoded Base 10 doing += instead of = (half asleep)
- Solution 1: Splicing Delimiter with Catchup 2 pointers - Two Pointers/Catchup
- Solution 2: Base 10 Auxiliary Length Delimiter with 1 pointer - Two Pointers/One Pointer with Auxiliary State
167. Two Sum II Sorted Array ::2:: - Medium
- Intro
- Abstraction
- Space & Time Complexity
- Brute Force (all pairs comparison)
- Find the Bug: Binary Search updates left and right pointer by midValue instead of midIndex
- Solution 1: BinarySearch Per Element for Complement - Two Pointers/One Pointer with Auxiliary State
- Solution 2: Opposite Ends Pointer Shift by BinarySearch Modification for Target - Two Pointers/Opposite Ends
15. 3Sum ::2:: - Medium
- Intro
- Abstraction
- Space & Time Complexity
- Brute Force (all triplets comparison)
- Brute Force Hashmap Two Sum I Approach (No Sorting)
- Find the Bug: List is unHashable
- Find the Bug: Index Into Wrong Array (2x) [im half asleep rn ok? :) cut me some slack]
- Find the Bug: Giving Sorted() 3 arguments instead of 1 [i dont know python syntax, YET :)]
- Find the Bug: Adding Set to Set, cannot because set is un-hashable type [again, syntax]
- Find the Bug: Did not increment pointers if res == 0 case
- Solution 1: Mimicking Two Sum by doing Per Element Opposite Ends Pointer Shift by BinarySearch Modification for 0 (Sorting) - Two Pointers/K Pointer Variants
- Solution 2: Grouping By Parity 4 Triplet Combinations (time limit exceeded) - Two Pointers/Algorithm
42. Trapping Rain Water ::3:: - Hard
- Intro
- Abstraction
- Space & Time Complexity
- Brute Force
- Find the Bug: Complete misunderstanding of water heights (haha)
- Find the Bug: Two Pointers Early Break
- Find the Bug: Not checking if left wall exists after pop
- Find the Bug: Overwriting variables accidentally
- Find the Bug: Bad For Loop syntax
- Solution 1: Monotonic Traversal 2 Outer/2 Inner Pointers Creating Bounds Opposite Ends Pointer Shift by BinarySearch Modification (Sorting) - Two Pointers/K Pointer Variants
- Solution 2: Monotonic Stack - Two Pointers/Algorithm
- Solution 3: Dynamic Programming - Two Pointers/Algorithm
5. Longest Palindromic Substring ::2:: - Medium
- Intro
- Abstraction
- Find the Bug: Did not create Expanded String
- Find the Bug: Defined List instead of Slicing
- Find the Bug: Bad iteration leading to out of bounds on string expansion
- Find the Bug: Bad enumerate method:
- Solution 1: Manacher's Algorithm (iterate, mirror radius optimization, and expand) - Two Pointers/Algorithm
- Solution 2: Expand Around Center checking for Odd and Even palindromes (constant space) - Two Pointers/Algorithm
Two Pointers Intro
Leetcode problems with elegant 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
Use a single pointer to scan linearly and keep track of additional state variables to simulate a second pointer.
Ex: Move all zeros while maintaining order
def move_zeros(nums: list[int]) -> None:
# `last_non_zero_found_at` tracks the position where the next non-zero
# element should be placed, simulating a second pointer.
last_non_zero_found_at = 0
for current in range(len(nums)):
if nums[current] != 0:
nums[last_non_zero_found_at], nums[current] = nums[current], nums[last_non_zero_found_at]
last_non_zero_found_at += 1
# arr = [0, 1, 0, 3, 12]
# move_zeros(arr) Output: [1, 3, 12, 0, 0]Two Pointers Application: Opposite Ends
We can have two pointers starting at opposite ends of a list and move them inward while validating some sort of logic.
Ex: Determine if a string is a palindrome
def is_palindrome(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
# Example:
print(is_palindrome("radar")) # Output: True
print(is_palindrome("hello")) # Output: FalseTwo Pointers Application: Sliding Window
We can have two pointers represent a window over a sequence that expands or shrinks to satisfy a condition.
Ex: Find the length of the longest substring without repeating characters.
def longest_unique_substring(s: str) -> int:
char_set = set()
left = 0
maxLength = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
maxLength = max(maxLength, right - left + 1)
return maxLength
# Example:
print(longest_unique_substring("abcabcbb")) # Output: 3Two Pointers Application: Fast & Slow Pointers
We can have have two pointers moving at different speeds to detect cycles or find midpoints in linked lists or arrays.
Ex: Detect a cycle in a linked list.
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
def has_cycle(head: ListNode) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Example:
# Construct a list with a cycle: 1 -> 2 -> 3 -> 4 -> 2 (cycle)
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2
print(has_cycle(node1)) # Output: TrueTwo Pointers Application: Partitioning
We can have two pointers in the same array moving inward/outward to rearrange elements based on a condition.
Ex: Move all zeros in an array to the end while maintaining the order of other elements
def move_zeros(nums):
left, right = 0, 0
while right < len(nums):
if nums[right] != 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right += 1
return nums
# Example:
print(move_zeros([0, 1, 0, 3, 12])) # Output: [1, 3, 12, 0, 0]Two Pointers Application: Parallel Pointer Traversal
We can have two pointers traversing two separate arrays in parallel to merge, compare, or find intersections.
Ex: Merge two sorted arrays into one sorted array
def merge_sorted_arrays(arr1, arr2):
result = []
i, j = 0, 0
while i < len(arr1) and j < len(arr2):
if arr1[i] < arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
result.extend(arr1[i:])
result.extend(arr2[j:])
return result
# Example:
print(merge_sorted_arrays([1, 3, 5], [2, 4, 6])) # Output: [1, 2, 3, 4, 5, 6]Two Pointers Application: Catchup
We have two pointers traversing one array. One remains frozen, but catches up to the other after logic is complete on a subsection.
Ex: Decode Two Pointer Splicing
Two Pointers Application: K Pointer Variants
We can extend the two pointer case to track k pointers simultaneously. These pointers can traverse the same list, different lists, or freeze while moving other pointers.
Ex: Given an integer array nums, return all the unique triplets [nums[i], nums[j], nums[k]] that sum to 0.
def threeSum(nums):
nums.sort() # Step 1: Sort the array
result = []
for i in range(len(nums)):
# Avoid duplicates for the first element
if i > 0 and nums[i] == nums[i - 1]:
continue
# Two-pointer approach
left, right = i + 1, len(nums) - 1
while left < right:
current_sum = nums[i] + nums[left] + nums[right]
if current_sum == 0:
result.append([nums[i], nums[left], nums[right]])
# Move pointers and 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
elif current_sum < 0:
left += 1 # Increase sum by moving left pointer rightward
else:
right -= 1 # Decrease sum by moving right pointer leftward
return result
# Example usage:
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums)) # Output: [[-1, -1, 2], [-1, 0, 1]]Two Pointers Application: Algorithm
Case where a problem that seems to require Two Pointers is easily solved by an algorithm specifically made for that problem
Ex: Manacher's Algorithm, find the 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 = 2 * center - i # Mirror of `i` with respect to `center`
# If within bounds of the current right boundary
if i < right:
p[i] = min(right - i, p[mirror])
# Expand around `i`
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))
start = (centerIndex - maxLen) // 2 # Convert index back to original string
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.
We can convert the string s into lowercase, traverse using pointers comparing characters on the start and end of the string.
Space & Time Complexity
| Solution | Time Complexity | Space Complexity | Time Remark | Space Remark |
|---|---|---|---|---|
| Brute Force One 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 | 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) |
Brute Force One Pointer
def isPalindrome(self, s: str) -> bool:
# space complexity: list to store cleaned string of n length O(n)
cleaned = []
# simple way for alphaNum check
def alphaNum(c):
return (ord('A') <= ord(c) <= ord('Z') or
ord('a') <= ord(c) <= ord('z') or
ord('0') <= ord(c) <= ord('9'))
# time complexity: iterate over string of n length O(n)
for c in s:
if alphaNum(c):
if 'A' <= c <= 'Z':
cleaned.append(chr(ord(c) + 32))
else:
cleaned.append(c)
# time complexity: two pointer iteration of string of n length O(n)
n = len(cleaned)
for i in range(n // 2):
if cleaned[i] != cleaned[n - i - 1]:
return False
# overall: time complexity O(n)
# overall: space complexity O(n)
return TrueFind the Bug: Less than instead of Less than or equal to
def isPalindrome(self, s: str) -> bool:
# INCORRECT:
# 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'))
# INCORRECT:
# 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 TrueFind the Bug: Not Moving Pointers (thinking we are)
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 TrueFind the Bug: Missing Char Palindrome Comparison (again, im half asleep, my bad :) ]
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)
# INCORRECT:
# missing char comparison
l += 1
r -= 1
return TrueSolution 1: Slicing Traversing in Reverse Order - Two Pointers/Algorithm
def isPalindrome(self, s: str) -> bool:
# space complexity: cleaned version of string of n length O(n)
phrase = ""
# time complexity: iterate over string of n length O(n)
for c in s:
if c.isalnum():
phrase += c.lower()
# slicing
# [start:stop:step]
# [::-1]
# here start and stop are omitted, so the slice includes the entire sequence
# step is -1, which indicates that sequences should be traversed in reverse order
# phrase is traversed left to right
# phrase[::-1] is traversed right to left
return phrase == phrase[::-1]| Aspect | Time Complexity | Space Complexity | Time Remarks | Space Remarks |
|---|---|---|---|---|
| Cleaned list | O(n) | O(n) | Iterate over list of n length O(n) | Memory allocation to store clean string of n length O(n) |
| Palindrome Check | O(n) | O(1) | Comparison operation of two chars takes constant O(1) for string of n length O(n) | No additional memory allocation for comparison or iteration O(1) |
| Overall | O(n) | O(n) | Iterating over list of n length dominates leading to O(n) | Memory allocation to store clean string of n length dominates leading to O(n) |
Solution 2: Pre Clean Opposite Ends Comparison - Two Pointers/Opposite Ends
def isPalindrome(self, s: str) -> bool:
# space complexity: cleaned version string of n length O(n)
cleaned = []
# isAlphaNum check using ord()
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)
# time complexity: iterate over string of n length O(n)
for c in s:
# skip until isAlphaNum char
if isAlphaNum(c):
# Convert to lowercase char
if isUpper(c):
cleaned.append(toLower(c))
else:
cleaned.append(c)
# clean is now lowercase alphaNum
# compare using left and right pointers
# time complexity: iterate over list of n length O(n)
left, right = 0, len(cleaned) - 1
while left < right:
if cleaned[left] != cleaned[right]:
return False
left += 1
right -= 1
# overall: time complexity O(n)
# overall: space complexity O(n)
return True| Aspect | Time Complexity | Space Complexity | Time Remarks | Space Remarks |
|---|---|---|---|---|
| Cleaned list | O(n) | O(n) | Iterating over list of n length O(n) | Memory allocation to store clean string of n length O(n) |
| Two Pointer | O(n) | O(1) | Comparison operation of two chars takes constant O(1) for string of n length O(n) | No additional memory allocation for comparison or iteration O(1) |
| Overall | O(n) | O(1) | Iterating over list of n length dominates leading to O(n) | No additional memory allocation for comparison O(1) |
Solution 3: In Place Opposite Ends Comparison - Two Pointers/Opposite Ends
def isPalindrome(self, s: str) -> bool:
# isAlphaNum check using ord()
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)
# space complexity: no additional space used for storage O(1)
left, right = 0, len(s) - 1
# time complexity: iteration over string of n length O(n)
while left < right:
# time complexity: move left and right to isAlphaNum char O(n)
while left < right and not isAlphaNum(s[left]):
left += 1
while left < right and not isAlphaNum(s[right]):
right -= 1
# Convert left and right to lowercase char
leftChar = s[left]
rightChar = s[right]
if isUpper(leftChar):
leftChar = toLower(leftChar)
if isUpper(rightChar):
rightChar = toLower(rightChar)
# Compare left and right char
if leftChar != rightChar:
return False
# move pointers
left += 1
right -= 1
# overall: time complexity O(n)
# overall: space complexity O(1)
return True| Aspect | Time Complexity | Space Complexity | Time Remarks | Space Remarks |
|---|---|---|---|---|
| Two Pointer | O(n) | O(1) | Comparison operation of two chars takes constant O(1) for string of n length O(n) | No additional memory allocation for comparison or iteration O(1) |
| Overall | O(n) | O(1) | Iterating over string n length dominates leading to O(n) | No additional memory 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. The encoded string is then decoded back to the original list of strings Please implement encode and decode. strs[i] contains only UTF-8 characters.
| Input | Output |
|---|---|
| ["leet", "code", "love", "you"] | ["leet", "code", "love", "you"] |
| ["we", "say", ":", "yes"] | ["we", "say", ":", "yes"] |
Constraints:
Abstraction
We need to create an encode and decode function and mark the start of a new string as well as its length.
Space & Time Complexity
| Solution | Time Complexity | Space Complexity | Time Remark | Space Remark |
|---|---|---|---|---|
| Two Pointers Length Delimiter |
Find the 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
# INCORRECT:
# 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 decodedFind the 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] != "#":
# INCORRECT:
# 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 decodedSolution 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 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 n strings 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):
# update right pointer to start of next (delim + string) group
right = left
# grab length before delimiter
while encoded[right] != "#":
right += 1
# right is now pointing at delim
# [ 2 # h i ... ]
# ^ ^
# l r
# splicing the length of the string
length = int(encoded[left:right])
right += 1
# skip delimiter, point to start of string
# [ 2 # h i ... ]
# ^ ^
# l r
# 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])
# splicing the string of 'length' characters
# [ 2 # h i 4 # ...]
# [ 0 1 2 3 4 5 6 ...]
# ^ ^ ^
# l r r'
# 2 + 2 = 4, start of length in next delimiter group
left = right + length
# left pointing to start of next len
# [ 2 # h i 4 # ...]
# [ 0 1 2 3 4 5 6 ...]
# ^ ^
# r l
# 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(n2) | O(n2) | Iterating over list of n strings of n n length O(n) | Memory allocation for encoded string of length O(n) |
| Decode loop | O(n2) | O(n2) | Iterate over encoded n strings with delimiter n length o(n) | Memory allocation for list of strings n length |
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(n2) | O(n2) | Iterating over list of n strings of n n length O(n) | Memory allocation for encoded string of length O(n) |
| Decode loop | O(n2) | O(n2) | Iterate over encoded n strings with delimiter n length o(n) | Memory allocation for list of strings n length |
167. Two Sum II Sorted Array ::2:: - Medium
Topics: Array, Two Pointers, Binary Search
Intro
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. 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:
Your solution must use only constant extra space O(1)
Abstraction
Given a sorted array, find two numbers which add up to target.
Unlike Two Sum I, we do not neccesarrily have to traverse the entire array, as since the given array is sorted, we can make assumptions about our traversal using l and r pointers.
Space & Time Complexity
| Solution | Time Complexity | Space Complexity | Time Remark | Space Remark |
|---|---|---|---|---|
| Brute Force (all pair comparison) | O(n2) | O(1) | For each pair of elements, we compare them, leading to quadratic number of comparison O(n2) | No additional memory allocation O(1) |
| 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) |
Brute Force (all pairs comparison)
def twoSumII(self, numbers: List[int], target: int) -> List[int]:
# time complexity: iteration of O(n)
for i in range(len(numbers)):
# time complexity: iteration of O(n^2)
for j in range(i + 1, len(numbers)):
# time complexity: sum and comparison operations take constant O(1)
if numbers[i] + numbers[j] == target:
return [i + 1, j + 1] # Convert to 1-indexed
# overall: time complexity O(n^2)
# 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) |
| Inner loop | O(n2) | O(1) | For each element in the outer loop, the inner loop iterates through all subsequent elements with Big(O) is O(n2). Derivation here | No additional memory allocation for iteration O(1) |
| Comparison | O(1) | O(1) | Sum and comparison operations in constant O(1) | No additional memory allocation for sum or comparison O(1) |
| Overall | O(n2) | O(1) | The inner loop dominates leading to O(n2) time complexity | No additional memory was allocated leading to constant O(1) space complexity. |
Find the 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]
# INCORRECT:
# moving pointer based on int value, instead of index
elif currComplementTarget < midInt:
right = midInt - 1
# INCORRECT:
# 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 resFind 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 resSolution 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(n2) | O(1) | Two pointer traversal for subarray search over n elements O(n) per outer iteration n O(n), leading to O(n2) | 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(n2) | O(n) | Two pointer traversal for n elements dominates, leading to O(n2) | 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(n2) | O(n) | Outer/Inner iteration over list of negative numbers O(n2) with inverse positive lookup O(1), leading to O(n2) | Adding n/3 triplets to result O(n/3), leading to O(n) |
| Positive Pairs | O(n2) | O(n) | Outer/Inner iteration over list of positive numbers O(n2) with inverse positive lookup O(1), leading to O(n2) | Adding n/3 triplets to result O(n/3), leading to O(n) |
| Overall | O(n2) | O(n) | Negative and positive iterations dominate leading to O(n2) | 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(n2) | O(1) | Iteration over list of n length per iteration in outer loop O(n2) | 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(n2) | O(1) | Inner loop dominates leading to O(n2) | 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 waterFind 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 waterFind 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 waterFind 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 waterFind 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 waterSolution 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) |
5. Longest Palindromic Substring ::2:: - Medium
Topics: Two Pointers, String, Dynamic Programming
Intro
Given a string s, return the longest palindromic substring in s.
| Input | Output |
|---|---|
| "cbbd" | "bb" |
| "babad" | "bab" or "aba" |
Constraints:
1 ≤ s.length ≤ 1000
s consists of only digits and English letters.
Abstraction
Find the longest palindrome in a string.
Find the Bug: Did not create Expanded String
def longestPalindrome(self, s: str) -> str:
# INCORRECT:
# did not create expandedStr
# did not solve odd vs even palindrome problem
# missing:
# expandedStr = "#".join(f"^{s}$")
center = 0
right = 0
n = len(s)
p = [0] * n
for i in range(1, n-1):
# 1
mirror = (2*center) - i
# 2
if i < right:
p[i] = min(right-i, p[mirror])
# 3
while s[i + p[i] + 1] == s[i - p[i] - 1]:
p[i] += 1
# 4
if i + p[i] > right:
center = i
right = i + p[i]
(maxRadius, center) = max((maxRadius, i) for (i, maxRadius) in enumerate(p))
start = (center-maxRadius) // 2
return s[start:start+maxRadius]Find the Bug: Defined List instead of Slicing
def longestPalindrome(self, s: str) -> str:
def expandAroundCenter(left, right):
while left >= 0 and right < n and s[left] == s[right]:
left -= 1
right += 1
# INCORRECT:
# defined list instead of slicing
# should be: s[left+1:right]
return s[left+1, right]
n = len(s)
maxPalin = ""
for i in range(n):
oddPalin = expandAroundCenter(i, i)
evenPalin = expandAroundCenter(i, i+1)
if len(oddPalin) > len(maxPalin):
maxPalin = oddPalin
if len(evenPalin) > len(maxPalin):
maxPalin = evenPalin
return maxPalinFind the Bug: Bad iteration leading to out of bounds on string expansion
def longestPalindrome(self, s: str) -> str:
expandedStr = "#".join(f"^{s}$")
n = len(expandedStr)
p = [0] * n
center = 0
right = 0
# INCORRECT:
# iteration will also expand from the sentinals '^' and '$'
for i in range(n):
# grab mirror
mirror = (2*center)-i
# validate mirror
if i < right:
p[i] = min(p[mirror], (right-i))
# expand
# INCORRECT:
# due to iteration, expansion is not guaranteed and prevent
# out of bounds grab, since we are missing the eventual
# '^' != '$'
while expandedStr[i - p[i] - 1] == expandedStr[i + p[i] + 1]:
p[i] += 1
# find new right most
if p[i] + i > right:
center = i
right = p[i] + i
# translate back to height
maxRadi, center = max((maxRadi, center) for (center, maxRadi) in enumerate(p))
startIndex = (center-maxRadi)//2
return s[startIndex:startIndex+maxRadi]Find the Bug: Bad enumerate method:
def longestPalindrome(self, s: str) -> str:
expandedStr = "#".join(f"^{s}$")
n = len(expandedStr)
p = [0] * n
center = 0
right = 0
for i in range(1, n-1):
# grab mirror
mirror = (2*center)-i
# validate mirror
if i < right:
p[i] = min(p[mirror], (right-i))
# expand
while expandedStr[i - p[i] - 1] == expandedStr[i + p[i] + 1]:
p[i] += 1
# find new right most
if p[i] + i > right:
center = i
right = p[i] + i
# translate back to height
# INCORRECT:
# should be
# enumerate(p)
# instead of p.enumerate()
maxRadi, center = max((maxRadi, center) for (center, maxRadi) in p.enumerate())
startIndex = (center-maxRadi)//2
return s[startIndex:startIndex+maxRadi]Solution 1: Manacher's Algorithm (iterate, mirror radius optimization, and expand) - Two Pointers/Algorithm
def longestPalindrome(self, s: str) -> str:
# Note:
# Preprocessing with #, ^, and $:
# '#': ensures uniform expansion, for both odd and even length palindromes
# '^' and '$': sentinel characters don't match valid input characters, serve as true start and end markers
# '#': ensures all palindromes start and end with '#'
# '#': occur on odd indexes
# Mapping:
# we can map odd '#' indexes to their even character:
# mapping '#' at index 1 to char pair 'a' at index 2, to original 'a' at index 0
# [ ^ # a # b # a # $ ] -> [ a b a ] via : originalStart = (expandedCenter - radius) / 2
# 0 1 2 3 4 5 6 7 8 0 1 2 thus: originalStart = (4 - 3) / 2 = 0
# Boundary expansion:
# For any index i, center of palindrome at i can either be:
# - character from the original string
# - placeholder '#'
# Center definition allows even length palindromes such as "abba", see below,
# to have a single middle point, allowing the same expanding logic
# for even and odd strings for palindrome validation
# Ex:
# ^ # a # b # b # a # $ || new string len 11,
# 0 1 2 3 4 5 6 7 8 9 10 ||
# ^ || index 5 center for even length "abba"
# index 1 palindrome: "#"
# index 2 palindrome: "#a#"
# index 5 palindrome: "#a#b#b#a#"
# etc...
expandedStr = "#".join(f"^{s}$")
n = len(expandedStr)
# Right Most Palindrome and Mirror Trick:
# Iteration tracks the right boundary for the current farthest right palindromic substring,
# which allows us to take advantage of the mirror radius trick.
# It speeds up palindrome expansion by starting the current palindrome radius
# at the radius value of its mirror
# p[i]: radius of palindrome centered at some index i
p = [0] * n
# mirror radius validation: tracking right boundary
# right: right boundary of the current right most palindrome
right = 0
# mirror radius validation: tracking center of right most in order to calculate mirror index
# center: center index of the current right most palindrome
center = 0
# iteration range ignores sentinel indexes 0 and (n-1): ^ and $
# i: center of current palindrome
# time complexity: iterate over list of n length O(n)
for i in range(1, n - 1):
# mirror:
# i is current index being processed
# i is to the right of center and has a mirror to the left of center
# ex: center = 6, i = 7 => mirror = (2 * 6) - 7 = 5
mirror = (2 * center) - i
# mirror radius validation:
# if i lies within bounds of the right most palindrome,
# the right most palindrome symmetry guarantees that the palindrome radius
# for the mirror of i, is applicable to i as well,
# while within the bounds of the right most palindrome
if i < right:
# mirror radius is either:
# - less than the distance between i and right bound,
# in which case all of the radius is valid
# - exceeds bounds and is farther than right bound,
# in which case only the radius up until the right bound is valid
# i radius is thus, bounded by minimum between:
# - mirror radius
# - distance from i to the right bound
p[i] = min(right - i, p[mirror])
# assumption: if valid mirror, we pre-set p[i] to p[mirror]
# now expand: expand radius p[i] until palindromic status is broken
while expandedStr[i + p[i] + 1] == expandedStr[i - p[i] - 1]:
p[i] += 1
# p[i]: radius for palindrome at i
# i: center for palindrome at i
# check: if we have a new right most boundary, update center and right
if i + p[i] > right:
right = i + p[i]
center = i
# expandedStr iteration complete:
# p[] stores radius of palindrome centered at each index
# scan p[] grabbing max palindrome radius alongside its center
maxRadius, centerIndex = max((palindromeRadius, i) for (i, palindromeRadius) in enumerate(p))
# Note:
# index and radius are relative to expandedStr, not the original string
# thus, we need to translate to original string indexes
# Notice, how in the expanded string,
# - all original characters are on even index
# - all original characters have matching # on the left odd index
# abba => ^ # a # b # b # a # $ | a=2, b=4, b=6, a=8
# 0123 => 0 1 2 3 4 5 6 7 8 9 10 | #=1, #=3, #=5, #=7
# aba => ^ # a # b # a # $ | a=2, b=4, a=6
# 012 => 0 1 2 3 4 5 6 7 8 | #=1, #=3, #=5
# any palindrome will always end with a '#'.
# so if we divide the starting odd position by 2, it will always map
# to an original character.
# so an easy translation formula is:
start = (centerIndex - maxRadius) // 2
# splice longest substring
# overall: time complexity O(n)
# overall: space complexity O(n)
return s[start: start + maxRadius]| Aspect | Time Complexity | Space Complexity | Time Remarks | Space Remarks |
|---|---|---|---|---|
| Preprocessing | O(n) | O(n) | Building expanded string | Memory allocation for processed string O(n) |
| Iterating | O(n) | O(1) | Iterate over processed string of n length O(n) | No additional memory allocation for iteration O(1) |
| Expanding radii | O(n) | O(n) | Radius expansion over processed string of n length O(n) | Radius array to store radii for each index for string of n length O(n) |
| Updating mirror bounds | O(1) | O(1) | Updating center and right for right most palindrome in constant O(1) | No additional memory allocation for center and right variables O(1) |
| Overall | O(n) | O(n) | Iterating over expanded string dominates, leading to O(n) time complexity. | Expanding string dominates, leading to O(n) space complexity. |
Solution 2: Expand Around Center checking for Odd and Even palindromes (constant space) - Two Pointers/Algorithm
def longestPalindrome(self, s: str) -> str:
# expand from a given left and right while
# maintaining palindrome property
def expandAroundCenter(left, right):
while left >= 0 and right < n and s[left] == s[right]:
left -= 1
right += 1
# curr iteration is not valid:
# ignore left: incrementing index
# ignore right: noninclusive right slicing
return s[left+1:right]
n = len(s)
maxPalindrome = ""
# time complexity: iterate over list of n length O(n)
for i in range(n):
# odd expansion, centered at i
oddPalindrome = expandAroundCenter(i, i)
# even expansion, centered at i and i + 1
evenPalindrome = expandAroundCenter(i, i+1)
# update longest
if len(oddPalindrome) > len(maxPalindrome):
maxPalindrome = oddPalindrome
if len(evenPalindrome) > len(maxPalindrome):
maxPalindrome = evenPalindrome
# overall: time complexity O(n^2)
# overall: space complexity O(1)
return maxPalindrome| Aspect | Time Complexity | Space Complexity | Time Remarks | Space Remarks |
|---|---|---|---|---|
| Iterating | O(n) | O(1) | Iterating over list of n length O(n) | No additional memory allocation for iteration O(1) |
| Odd expansion | O(n^2) | O(1) | For each center, expands outward for odd length palindromes n length O(n), for each outer iteration O(n), leading to O(n^2) | No additional memory allocation needed during expansion O(1) |
| Even expansion | O(n^2) | O(1) | For each center, expands outward for even length palindromes n length O(n), for each outer iteration O(n), leading to O(n^2) | No additional memory allocation needed during expansion O(1) |
| Updating longest | O(1) | O(1) | Comparing odd and even length palindrome to current max in constant O(1) | No additional memory allocation needed for comparison to current max O(1) |
| Overall | O(n^2) | O(1) | Even and odd expansion per outer iteration dominate, leading to O(n2) | No additional memory allocation required for in place expansion or iteration, leading to constant O(1) |