Array / String
Notes
Ways to process an array:
-
Loop forwards or backwards
-
Sort
-
Reverse
-
Check neighbor indices (e.g.
arr[n + 2]) -
Get frequency with bucket sort or hashmap
-
Combinations of the above
Merge Sorted Array (Easy)
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ i = len(nums1) - 1 i1 = m - 1 i2 = n - 1 # Iterate backwards until nums2 is empty while i2 >= 0: if i1 >= 0 and nums1[i1] >= nums2[i2]: nums1[i] = nums1[i1] i1 -= 1 else: nums1[i] = nums2[i2] i2 -= 1 i -= 1
Time: O(n)
Space: O(1)
Remove Element (Easy)
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k. Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums. Return k.
def removeElement(nums: List[int], val: int) -> int: k = 0 # Swap all non-vals to nums[k] for i in range(len(nums)): if nums[i] != val: nums[i], nums[k] = nums[k], nums[i] k += 1 return k
Time: O(n)
Space: O(1)
Remove Duplicates from Sorted Array (Easy)
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.
Consider the number of unique elements in nums to be k. After removing duplicates, return the number of unique elements k.
def removeDuplicates(nums: List[int]) -> int: k = 1 # Slot into nums[k] if not duplicate for i in range(1, len(nums)): if nums[i] > nums[i - 1]: nums[k] = nums[i] k += 1 return k
Time: O(n)
Space: O(1)
Majority Element (Easy)
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than n / 2 times. You may assume that the majority element always exists in the array.
Follow-up: Solve the problem in linear time and constant space.
def majorityElement(nums: List[int]) -> int: answer = nums[0] count = 0 # If an answer always exists, its count will always be # greater than the total count of all other values for num in nums: if num == answer: count += 1 else: count -= 1 if count == 0: answer = num count = 1 return answer
Time: O(n)
Space: O(1)
Best Time to Buy and Sell Stock (Easy)
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
def maxProfit(prices: List[int]) -> int: profit = 0 minPrice = prices[0] for i in range(1, len(prices)): profit = max(profit, prices[i] - minPrice) minPrice = min(minPrice, prices[i]) return profit
Time: O(n)
Space: O(1)
This problem is similar to finding a maximum subarray using Kadane's algorithm.
def maxSubarray(nums: List[int]) -> int: bestSum = currentSum = 0 for x in nums: # If x is low enough to make the current sum negative, # expanding the current subarray is useless. # Reset to 0 for new subarray. currentSum = max(0, currentSum + x) bestSum = max(bestSum, currentSum) return bestSum
Time: O(n)
Space: O(1)
Roman to Integer (Easy)
Roman numerals are represented by seven different symbols: I (1), V (5), X (10), L (50), C (100), D (500), and M (1000).
I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
def romanToInt(s: str) -> int: m = { "I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000 } answer = 0 # If the next char is greater than current char, subtract instead of add for i in range(len(s) - 1): if m[s[i]] < m[s[i + 1]]: answer -= m[s[i]] else: answer += m[s[i]] answer += m[s[-1]] return answer
Time: O(n)
Space: O(1)
Length of Last Word (Easy)
Given a string s consisting of words and spaces, return the length of the last word in the string.
A word is a maximal substring consisting of non-space characters only.
s consists of only English letters and spaces ' '. There will be at least one word in s.
def lengthOfLastWord(s: str) -> int: right = len(s) - 1 while s[right] == " ": right -= 1 left = right - 1 while left >= 0 and s[left] != " ": left -= 1 return right - left
Time: O(n)
Space: O(1)
Longest Common Prefix (Easy)
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
def longestCommonPrefix(strs: List[str]) -> str: if len(strs) == 0: return "" for i in range(len(strs[0])): for word in strs: if i >= len(word) or word[i] != strs[0][i]: return strs[0][:i] return strs[0]
Time: O(n * m) where m is length of shortest word
Space: O(1)
Find the Index of the First Occurrence in a String (Easy)
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
def strStr(haystack: str, needle: str) -> int: def isMatch(needle, haystack, start, end): if len(needle) != (end - start + 1): return False for i in range(len(needle)): if needle[i] != haystack[start]: return False start += 1 return True # check for match when sliding window is correct size start = 0 for end in range(len(haystack)): if (end - start + 1) == len(needle): if isMatch(needle, haystack, start, end): return start start += 1 return -1
Time: O(n * m) where n = len(haystack), m = len(needle)
Space: O(1)
There is an alternative solution with O(n + m) time and O(m) space using the Knuth–Morris–Pratt algorithm.
Remove Duplicates from Sorted Array II (Medium)
Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
If there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
def removeDuplicates(nums: List[int]) -> int: k = 2 # k = index of next duplicate to be replaced for n in range(2, len(nums)): if nums[n] > nums[k - 2]: nums[k] = nums[n] k += 1 return k
Time: O(n)
Space: O(1)
Rotate Array (Medium)
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
def rotate(nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ def reverseList(li, l, r): while l < r: li[l], li[r] = li[r], li[l] l += 1 r -= 1 k = k % len(nums) reverseList(nums, 0, len(nums) - 1) reverseList(nums, 0, k - 1) reverseList(nums, k, len(nums) - 1)
Time: O(n)
Space: O(1)
Best Time to Buy and Sell Stock II (Medium)
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
def maxProfit(prices: List[int]) -> int: profit = 0 buy = prices[0] # If positive profit, sell # Else update to new minimum buy price for price in prices: if price > buy: profit += price - buy buy = price return profit
Time: O(n)
Space: O(1)
Jump Game (Medium)
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
def canJump(nums: List[int]) -> bool: if len(nums) < 2: return True goal = len(nums) - 1 farthest = 0 for i in range(len(nums)): if nums[i] == 0 and i == farthest: return False farthest = max(farthest, i + nums[i]) if farthest >= goal: return True
Time: O(n)
Space: O(1)
Alternative solution:
def canJump(nums: List[int]) -> bool: farthest = 0 for num in nums: if farthest < 0: return False if num > farthest: farthest = num farthest -= 1 return True
Time: O(n)
Space: O(1)
Jump Game II (Medium)
You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where 0 <= j <= nums[i] and i + j < n.
Return the minimum number of jumps to reach nums[n - 1]. Assume there is always a way to reach nums[n - 1].
def jump(nums: List[int]) -> int: count = 0 position = 0 farthest = 0 # Exclude last index to prevent one extra count for i in range(len(nums) - 1): farthest = max(farthest, i + nums[i]) # Reached biggest possible jump. Update position if i == position: position = farthest count += 1 return count
Time: O(n)
Space: O(1)
H-Index (Medium)
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index.
The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
def hIndex(citations: List[int]) -> int: citations.sort(reverse = True) h = 0 for i in range(len(citations)): if citations[i] >= i + 1: h += 1 else: return h return h
Time: O(n log n)
Space: O(1) or O(n) due to python built-in sort()
Alternative solution
def hIndex(citations: List[int]) -> int: # Get frequency buckets = [0] * (len(citations) + 1) for count in citations: if count >= len(citations): buckets[-1] += 1 else: buckets[count] += 1 count = 0 for i in range(len(buckets) - 1, -1, -1): count += buckets[i] # Ex: count == i == 3 means at least 3 papers were cited 3 times if count >= i: return i return 0
Time: O(n)
Space: O(n)
Insert Delete GetRandom O(1) (Medium)
Implement the RandomizedSet class:
RandomizedSet()Initializes theRandomizedSetobject.bool insert(int val)Inserts an itemvalinto the set if not present. Returnstrueif the item was not present,falseotherwise.bool remove(int val)Removes an itemvalfrom the set if present. Returnstrueif the item was present,falseotherwise.int getRandom()Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
Implement the functions of the class such that each function works in average O(1) time complexity.
import random class RandomizedSet: def __init__(self): self.nums = [] self.indexMap = {} def insert(self, val: int) -> bool: if val in self.indexMap: return False self.nums.append(val) self.indexMap[val] = len(self.nums) - 1 return True def remove(self, val: int) -> bool: if val not in self.indexMap: return False # Replace val with last element in nums openIndex = self.indexMap[val] self.indexMap[self.nums[-1]] = openIndex self.nums[openIndex] = self.nums[-1] del self.indexMap[val] self.nums.pop() return True def getRandom(self) -> int: return random.choice(self.nums)
Product of Array Except Self (Medium)
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
Write an algorithm that runs in O(n) time and without using the division operation.
def productExceptSelf(nums: List[int]) -> List[int]: answer = [1] * len(nums) # Build prefix (product from left side of element) prefix = 1 for i in range(len(nums)): answer[i] = prefix prefix *= nums[i] # Build suffix and multiply with prefix suffix = 1 for i in range(len(nums) - 1, -1, -1): answer[i] *= suffix suffix *= nums[i] return answer
Time: O(n)
Space: O(1) excluding output
Gas Station (Medium)
There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.
def canCompleteCircuit(gas: List[int], cost: List[int]) -> int: if sum(gas) < sum(cost): return -1 # An answer is guaranteed at this point net = 0 answer = 0 for i in range(len(gas)): net += gas[i] - cost[i] # If net becomes negative, answer must be at least after i if net < 0: net = 0 answer = i + 1 return answer
Time: O(n)
Space: O(1)
Integer to Roman (Medium)
Seven different symbols represent Roman numerals with the following values:
I -> 1, V -> 5, X -> 10, L -> 50, C -> 100, D -> 500, M -> 1000
Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:
- If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the remainder to a Roman numeral.
- If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
- Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a symbol 4 times use the subtractive form.
Given an integer, convert it to a Roman numeral.
def intToRoman(num: int) -> str: pairs = [ (1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"), (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I") ] answer = [] for val, char in pairs: while num >= val: answer.append(char) num -= val return "".join(answer)
Time: O(n)
Space: O(1)
Reverse Words in a String (Medium)
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
def reverseWords(s: str) -> str: answer = [] left = right = len(s) - 1 # Loop backwards with two pointers. Find words, skip spaces while left >= 0: while left >= 0 and s[left] == " ": left -= 1 right = left if left < 0: break while left >= 0 and s[left] != " ": left -= 1 answer.append(s[left + 1: right + 1]) right = left return " ".join(answer)
Time: O(n)
Space: O(n)
Zigzag Conversion (Medium)
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this:
# P A H N # A P L S I I G # Y I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows.
def convert(s: str, numRows: int) -> str: if numRows == 1 or numRows == len(s): return s # Create buckets per row and add chars in order answer = [""] * numRows row = 0 direction = -1 for char in s: answer[row] += char if row == 0 or row == numRows - 1: direction *= -1 row += direction return "".join(answer)
Time: O(n)
Space: O(n)
Alternative solution:
# Draw outputs to find the pattern per row # rows = 3; gap = 4 rows = 4; gap = 6 rows = 5; gap = 8 # 0 4 8 12 0 6 12 0 8 # 1 3 5 7 9 11 13 1 5 7 11 13 1 7 9 # 2 6 10 2 4 8 10 2 6 10 # 3 9 3 5 11 13 # 4 12 def convert(s: str, numRows: int) -> str: if numRows == 1 or numRows >= len(s): return s # Add chars per row answer = [] gap = 2 * numRows - 2 # First row i = 0 while i < len(s): answer.append(s[i]) i += gap # Middle rows have alternating index offsets for i in range(1, numRows - 1): currI = i frontOffset = gap - i * 2 backOffset = gap - frontOffset while currI < len(s): answer.append(s[currI]) currI += frontOffset if currI < len(s): answer.append(s[currI]) currI += backOffset # Last row i = numRows - 1 while i < len(s): answer.append(s[i]) i += gap return "".join(answer)
Time: O(n)
Space: O(n)
Maximum Subarray (Medium)
Given an integer array nums, find the subarray with the largest sum, and return its sum.
def maxSubArray(nums: List[int]) -> int: # Kadane's algorithm answer, currSum = float("-inf"), 0 for num in nums: # num > currSum + num if currSum is negative currSum = max(currSum + num, num) answer = max(answer, currSum) return answer
Time: O(n)
Space: O(1)
Maximum Sum Circular Subarray (Medium)
Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.
A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].
A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.
def maxSubarraySumCircular(nums: List[int]) -> int: # Get contiguous mininum AND maximum subarrays for non-circular nums # If the answer is contiguous, then the answer was found # Otherwise, the answer is wrapping: # total = minSum + wrapped max sum ---> wrapped max sum = total - minSum # Note that this equation only applies because nums is circular total = 0 currMin = minSum = float("inf") currMax = maxSum = float("-inf") for num in nums: total += num currMin = min(currMin + num, num) minSum = min(minSum, currMin) currMax = max(currMax + num, num) maxSum = max(maxSum, currMax) # Edge case: If all nums are negative: (total - minSum == 0) and (maxSum < 0) if maxSum <= 0: return maxSum return max(maxSum, total - minSum)
Time: O(n)
Space: O(1)