NeedCode 150 Flashcards
(12 cards)
Longest Consecutive Sequence (Leetcode 128)
Problem:
Given an unsorted array of integers, return the length of the longest sequence of consecutive elements (e.g., [100, 4, 200, 1, 3, 2] → 4 for [1, 2, 3, 4]).
✅ Core Idea:
Use a hash set for O(1) lookups to track starts of sequences, and expand from there.
🧩 Key Insight (Interview Explanation):
You don’t need to sort (which is O(n log n)).
You only begin counting a sequence if the current number is the start of a sequence, meaning num - 1 is not in the set.
Then you expand forward using num + 1, num + 2, etc., checking the set for each.
This ensures each number is visited at most once.
🧠 How to think about it:
Instead of tracking subproblems, ask:
“When does it make sense to start a new sequence?”
If a number has no smaller neighbor, it’s the start.
Expand only from there.
📦 Time & Space Complexity:
Metric Value Why
Time O(n) Each number is visited at most once
Space O(n) Hash set stores all unique nums
🔤 Code Snippet:
python
Copy
Edit
def longestConsecutive(nums):
num_set = set(nums)
longest = 0
for num in num_set:
if num - 1 not in num_set: # only start at the beginning
current = num
streak = 1
while current + 1 in num_set:
current += 1
streak += 1
longest = max(longest, streak)
return longest 🧪 Example: Input: [100, 4, 200, 1, 3, 2] Set: {1, 2, 3, 4, 100, 200} Start at 1 → expand → 2 → 3 → 4 Length = 4
🔑 Interview Tip:
Emphasize that this is not a DP problem — it’s solved optimally with hashing and greedy expansion, avoiding redundant work by skipping non-starting elements.
🧠 Flashcard: Valid Sudoku (Leetcode 36)
Problem:
Given a 9×9 Sudoku board, determine if it is valid.
The board may be partially filled, but the rules must hold:
Each row must have digits 1–9 with no repeats
Each column must have digits 1–9 with no repeats
Each of the 9 3×3 sub-boxes must have digits 1–9 with no repeats
✅ Core Idea:
Use sets to track seen values in:
Each row
Each column
Each 3×3 box (indexed from 0 to 8)
🧠 How to think about it:
Ask: “How can I detect duplicates across rows, columns, and boxes in constant time?”
The answer: maintain three hash sets per constraint type, and check all filled cells once.
Use this formula to determine the box index:
box_idx = (row // 3) * 3 + (col // 3)
📦 Time & Space Complexity:
Metric Value Why
Time O(1) Always 9×9 = 81 iterations
Space O(1) Sets store at most 9 digits each
⚠️ While technically O(1), you should still demonstrate clean logic and organization in code.
🧪 Example Input:
python
Copy
Edit
[
[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”],
[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”],
…
]
🔤 Code Snippet:
def isValidSudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
val = board[r][c]
if val == '.':
continue
if val in rows[r] or val in cols[c] or val in boxes[(r // 3) * 3 + (c // 3)]:
return False
rows[r].add(val)
cols[c].add(val)
boxes[(r // 3) * 3 + (c // 3)].add(val)
return True 🔑 Interview Tip: "I use a hash set per row, column, and 3×3 box to track seen numbers. I compute the box index using integer division. If a number is ever duplicated within any group, I return False. Otherwise, after one pass through the board, I return True."
🧠 Flashcard: Product of Array Except Self (Leetcode 238)
Problem:
Given an integer array nums, return an array output such that output[i] is equal to the product of all elements of nums except nums[i], without using division, and in O(n) time.
✅ Core Idea:
Use prefix and suffix products:
First pass (left to right): store running prefix product in output[i]
Second pass (right to left): multiply in suffix product
You avoid division by building the result with only multiplications.
🧠 How to think about it:
“I need to build the product of all values except at index i.
I can split this into:
output[i] = product of nums[0..i-1] * product of nums[i+1..n-1].
I’ll compute the left part in the first pass, and the right part in the second pass.”
You can do both passes in a single output array using a temporary variable for the suffix.
📦 Time & Space Complexity:
Metric Value Why
Time O(n) Two single passes through array
Space O(1) Constant extra space (output not counted)
If interviewer allows using output array for storage, it’s O(1) space.
🧪 Example:
Input: [1, 2, 3, 4]
Prefix pass → [1, 1, 2, 6]
Suffix pass → [24, 12, 8, 6]
🔤 Code Snippet:
def productExceptSelf(nums):
n = len(nums)
output = [1] * n
# Left to right pass (prefix products)
for i in range(1, n):
output[i] = output[i - 1] * nums[i - 1]
# Right to left pass (suffix product rolling variable)
suffix = 1
for i in range(n - 1, -1, -1):
output[i] *= suffix
suffix *= nums[i]
return output 🔑 Interview Tip: "This problem looks like it needs nested loops or division, but it's actually solvable in two linear passes using prefix and suffix products. The trick is to accumulate one direction in-place and keep a rolling multiplier for the other direction."
🧠 Flashcard: Encode and Decode Strings (Leetcode 271)
Problem:
Design an algorithm to encode a list of strings into a single string, and decode it back into the original list.
You must handle strings that contain any characters, including #, digits, spaces, etc.
✅ Core Idea:
Prefix each string with its length, followed by a delimiter (like #), then the string itself.
This makes decoding easy:
Read the length up to #
Then grab the next length characters
This avoids ambiguity, even if strings contain special characters.
🧠 How to think about it:
“I can’t just use join with a delimiter like commas, because strings might contain those.
Instead, I’ll explicitly store the length of each string before the content so I know exactly how many characters to extract when decoding.”
📦 Time & Space Complexity:
Metric Value Why
Encode O(n) Every character is visited once
Decode O(n) Walk the encoded string linearly
Space O(n) New encoded string + decoded list
Where n is the total number of characters across all strings.
🔤 Code Snippet:
python
Copy
Edit
class Codec:
def encode(self, strs):
return ‘‘.join(f”{len(s)}#{s}” for s in strs)
def decode(self, s):
res = []
i = 0
while i < len(s):
j = i
while s[j] != '#':
j += 1
length = int(s[i:j])
j += 1 # move past '#'
res.append(s[j:j+length])
i = j + length
return res 🧪 Example:
Input: [“hello”, “world”]
Encoded: “5#hello5#world”
Decoded: [“hello”, “world”]
🔑 Interview Tip:
“Instead of relying on unreliable delimiters, I prefix each string with its length and a delimiter.
This guarantees correct parsing even when strings contain special characters, digits, or the delimiter itself.”
🧠 Flashcard: Top K Frequent Elements (Leetcode 347)
Problem:
Given an integer array nums and an integer k, return the k most frequent elements.
You must solve it in better than O(n log n) time.
✅ Core Idea:
Use a hash map to count frequencies, and then:
Option 1: use a min-heap of size k to keep track of top frequencies
Option 2: use bucket sort where index = frequency
🧠 How to think about it:
“Sort all elements by how often they appear — but full sorting would be O(n log n).
Instead, I’ll count frequencies in O(n) and either:
Use a heap to keep top k in O(n log k)
Or use bucket sort for linear time if needed.”
📦 Time & Space Complexity
Approach Time Space
Heap (n log k) O(n log k) O(n)
Bucket Sort O(n) O(n)
Where n = len(nums)
🔤 Code Snippet (Min-Heap):
import heapq
from collections import Counter
def topKFrequent(nums, k):
freq = Counter(nums)
return [num for num, _ in heapq.nlargest(k, freq.items(), key=lambda x: x[1])]
🔤 Code Snippet (Bucket Sort):
from collections import defaultdict, Counter
def topKFrequent(nums, k):
freq_map = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in freq_map.items():
buckets[freq].append(num)
res = []
for i in range(len(buckets) - 1, 0, -1):
for num in buckets[i]:
res.append(num)
if len(res) == k:
return res 🧪 Example:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
🔑 Interview Tip:
“I count frequencies with a hash map in O(n), then either use:
A min-heap to track the top k elements in O(n log k),
Or a bucket sort where index = frequency to get O(n) time.
Bucket sort is valid because frequency can’t exceed n.”
Flashcard: Group Anagrams (Leetcode 49)
Problem:
Given an array of strings strs, group the strings that are anagrams of each other.
An anagram is a word formed by rearranging the letters of another (e.g., “eat” and “tea”).
✅ Core Idea:
Use a hash map to group words by a shared anagram signature:
Either use the sorted version of the word as the key (tuple or string)
Or use a character count tuple as the key (to avoid sorting)
🧠 How to think about it:
“If two words are anagrams, then:
Their sorted versions are the same, or
Their letter frequency counts are the same.
I’ll use that as the key to group them in a hash map.”
📦 Time & Space Complexity
Approach Time Space
Sort-based key O(n·k log k) O(n·k)
Count-based key O(n·k) O(n·k)
Where:
n = number of words
k = max length of a word
🔤 Code Snippet (Sorted Key):
python
Copy
Edit
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for word in strs:
key = tuple(sorted(word))
groups[key].append(word)
return list(groups.values())
🔤 Code Snippet (Char Count Key — faster, avoids sorting):
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for word in strs:
count = [0] * 26
for char in word:
count[ord(char) - ord(‘a’)] += 1
groups[tuple(count)].append(word)
return list(groups.values())
🧪 Example:
Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
Output: [[“eat”,”tea”,”ate”],[“tan”,”nat”],[“bat”]]
🔑 Interview Tip:
“I use a hash map where the key is either the sorted string or a letter frequency tuple.
Both allow me to group anagrams efficiently.
The char-count version avoids sorting, giving O(n·k) time.”
🧠 Flashcard: Two Sum (Leetcode 1)
Problem:
Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.
Each input has exactly one solution, and you may not use the same element twice.
✅ Core Idea:
Use a hash map to store numbers you’ve seen and their indices.
As you iterate, check if the complement (target - num) is already in the map.
🧠 How to think about it:
“I’m looking for two numbers that sum to a target.
So for every number I see, I ask:
Have I already seen target - num?
If yes, that’s the pair.
If not, I store the current number for future lookup.”
📦 Time & Space Complexity:
Metric Value Why
Time O(n) One pass through list
Space O(n) Hash map stores up to n entries
🔤 Code Snippet:
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
🧪 Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] # because 2 + 7 = 9
🔑 Interview Tip:
“I use a hash map to track previously seen numbers and their indices.
On each iteration, I check whether the complement of the current number has already been seen.
If so, I return their indices immediately — ensuring O(n) time.”
🧠 Flashcard: Valid Anagram (LeetCode 242)
Problem
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An anagram means both strings contain the same characters in any order, with identical counts.
✅ Core Idea
Count and compare character frequencies. Two common approaches:
Sort & compare — sort both strings and check equality.
Hash map / array count — tally counts in one pass and verify in another.
🧠 How to think about it
“I need to confirm that every character in s appears the same number of times in t.
Sorting normalizes order, or I can build a frequency table for constant-time checks.”
📦 Time & Space Complexity
Approach Time Space
Sort & compare O(n log n) O(1) or O(n)*
Count array / map O(n) O(1)
- Sorting in-place can be O(1) extra, but if strings are immutable you’ll allocate new ones.
🔤 Code Snippet (Count Array)
def isAnagram(s: str, t: str) -> bool:
if len(s) != len(t):
return False
counts = [0] * 26
base = ord('a')
for ch in s:
counts[ord(ch) - base] += 1
for ch in t:
counts[ord(ch) - base] -= 1
if counts[ord(ch) - base] < 0:
return False
return True 🧪 Example
s = “anagram”
t = “nagaram”
→ True
s = “rat”
t = “car”
→ False
🔑 Interview Tip
“I prefer the frequency-count method: it’s O(n) time and uses a fixed–size array for lowercase letters, ensuring constant space. Sorting works too but incurs an O(n log n) penalty.”
Given an array height[] where each element represents the height of a vertical line at that index, choose two lines such that together with the x-axis, they form a container that holds the maximum amount of water. Return the maximum area of water that can be stored.
Input: height = [1,7,2,5,4,7,3,6]
Output: 36
Explanation: Container formed between heights[1] and heights[7] gives area = min(7, 6) * (7 - 1) = 6 * 6 = 36
🔍 Key Insight:
The shorter of the two lines determines the height of the container.
Area = min(height[i], height[j]) * (j - i)
You need to maximize this area.
✅ Optimal Solution: Two Pointer Approach
Initialize two pointers: i = 0, j = len(height) - 1
Calculate current area
Update max area if current is larger
Move the pointer pointing to the shorter line inward
Repeat until pointers meet
🕒 Time Complexity: O(n)
🧠 Space Complexity: O(1)
🔁 Why move the shorter line?
Because only increasing the minimum height has a chance to improve the area.
Moving the taller line won’t help (width shrinks, height stays limited by the shorter one).
✅ Python Code:
class Solution:
def maxArea(self, height: List[int]) -> int:
i, j = 0, len(height) - 1
maxArea = 0
while i < j:
area = min(height[i], height[j]) * (j - i)
maxArea = max(maxArea, area)
if height[i] < height[j]:
i += 1
else:
j -= 1
return maxArea
Given an array height[] representing an elevation map, compute how much water it can trap after raining.
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: Water is trapped in the valleys between bars.
🔍 Key Insight:
At any index i, the water trapped is:
min(max height to the left, max height to the right) - height[i]
✅ Approach: Prefix & Suffix Arrays
Create a prefix[] array: stores the tallest bar to the left of or at each position.
Create a suffix[] array: stores the tallest bar to the right of or at each position.
For every index i, trapped water = min(prefix[i], suffix[i]) - height[i]
Sum all trapped water values.
🕒 Time Complexity: O(n)
🧠 Space Complexity: O(n) (for prefix and suffix arrays)
✅ Python Code:
class Solution:
def trap(self, height: List[int]) -> int:
prefix = [0] * len(height)
suffix = [0] * len(height)
prefixMax = 0
suffixMax = 0
total = 0
for i in range(len(height)):
prefixMax = max(prefixMax, height[i])
prefix[i] = prefixMax
for i in range(len(height) - 1, -1, -1):
suffixMax = max(suffixMax, height[i])
suffix[i] = suffixMax
for i in range(len(height)):
total += min(prefix[i], suffix[i]) - height[i]
return total 🧠 Bonus Tip:
You can optimize space to O(1) using a two-pointer approach instead of prefix/suffix arrays.
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
leftMax, rightMax = 0, 0
total = 0
while left < right:
if height[left] < height[right]:
if height[left] >= leftMax:
leftMax = height[left]
else:
total += leftMax - height[left]
left += 1
else:
if height[right] >= rightMax:
rightMax = height[right]
else:
total += rightMax - height[right]
right -= 1
return total
Given an array prices[] where prices[i] is the price of a stock on the i-th day, find the maximum profit you can achieve by buying once and selling once later.
If you can’t make any profit, return 0.
Input: prices = [10,1,5,6,7,1]
Output: 6
Explanation: Buy at prices[1] = 1, sell at prices[4] = 7 → profit = 7 - 1 = 6
✅ Optimal Strategy:
Keep track of the lowest price seen so far (lowIdx)
At each day i, check if selling today yields a better profit:
profit = prices[i] - prices[lowIdx]
Update maxProfit if this is better
If today’s price is lower than prices[lowIdx], update lowIdx
🕒 Time Complexity: O(n)
🧠 Space Complexity: O(1)
✅ Python Code:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
lowIdx = 0
maxProfit = 0
for i in range(len(prices)):
if prices[i] < prices[lowIdx]:
lowIdx = i # Found a better buy price
else:
profit = prices[i] - prices[lowIdx]
maxProfit = max(maxProfit, profit)
return maxProfit
💡 Intuition:
Sweep through the array once, always asking:
“If I bought at the lowest price so far, is today a good day to sell?”
My own note:
Each new low price is a new bracket so to speak. You forget everything that happened before it and just continue on comparing later prices to this new lowest buy price. If you find a new solution that has a higher profit, you replace the old one with it.
Contains Duplicates
