all topics

Arrays & Hashing

Concatenation of Array

Return nums followed by nums again. [1,2,1] → [1,2,1,1,2,1].

1. Loop twice

  • Empty array.
  • Loop over nums, twice, appending each number.
python
class Solution:
    def getConcatenation(self, nums: List[int]) -> List[int]:
        arr = []
        for i in range(2):
            for num in nums:
                arr.append(num)
        return arr
timeO(n)spaceO(n)

2. Pre-size, single pass

  • Array of size 2n.
  • For each i: arr[i] = arr[i+n] = nums[i].
python
class Solution:
    def getConcatenation(self, nums: List[int]) -> List[int]:
        n = len(nums)
        arr = [0] * (2*n)
        for i, num in enumerate(nums):
            arr[i] = arr[i+n] = num
        return arr
timeO(n)spaceO(n)

3. nums * 2

  • Python repeats the list for you.
python
class Solution:
    def getConcatenation(self, nums: List[int]) -> List[int]:
        return nums * 2
timeO(n)spaceO(n)

Contains Duplicate

Does any value repeat? [1,2,3,1] → True. [1,2,3,4] → False.

Set

  • Empty set.
  • For each number: if it's already in the set, return True.
  • Otherwise, add it to the set.
  • Loop finishes with no hit → return False.
python
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        seen = set()
        for num in nums:
            if num in seen:
                return True
            seen.add(num)
        return False
timeO(n)spaceO(n)

Valid Anagram

Same letters, same counts, different order. "anagram" / "nagaram" → True.

1. Dict counts

  • Lengths differ → False, right away.
  • Count each letter in s, count each letter in t, one pass.
  • Compare the two counts.
python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
 
        if len(s)!=len(t):
            return False
 
        countS, countT = {}, {}
 
        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)
        
        return countS == countT
timeO(n)spaceO(1)

2. Fixed array, +1/−1

  • One array of 26 slots.
  • ord(ch) - ord('a') maps a letter to its index.
  • +1 at that index for every letter in s, -1 for every letter in t.
  • Every slot still 0 at the end → True.
python
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        
        count = [0]*26
 
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1
 
        for val in count:
            if val != 0:
                return False
        return True
timeO(n)spaceO(1)

Two Sum

Find two numbers in nums that add up to target, return their indices. nums = [2,7,11,15], target = 9 → [0,1].

1. Two-pass hash map

  • First pass: build a value → index map for all of nums.
  • Second pass: for each number, look up target - num in the map.
  • Found it, and it's not the same element → return both indices.
python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indices = {}
        
        for i,n in enumerate(nums):
            indices[n] = i
 
        for i,n in enumerate(nums):
            diff = target - n
            if diff in indices and indices[diff]!= i:
                return [i, indices[diff]]
 
        return []
timeO(n)spaceO(n)

2. One-pass hash map

  • One pass: for each number, check if target - num is already in the map.
  • Found it → return both indices, done.
  • Not found → add the current number to the map, keep going.
python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = {}
 
        for i, num in enumerate(nums):
            diff = target - num
            if diff in map:
                return [map[diff], i]
 
            map[num] = i
timeO(n)spaceO(n)

Longest Common Prefix

Find the longest prefix shared by every string in strs. ["flower","flow","flight"] → "fl".

Vertical scan

  • Walk character index i across strs[0].
  • At each i, check every other string in strs.
  • Out of bounds, or a character mismatch, at any string → stop, return the prefix built so far.
  • Never mismatches → strs[0] itself is the common prefix.
python
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        for i in range(len(strs[0])):
            for s in strs:
                if i == len(s) or s[i] != strs[0][i]:
                    return s[:i]
        return strs[0]
timeO(n*m)spaceO(1)

Group Anagrams

Group strings that are anagrams of each other. ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]].

Frequency array as key

  • For each string, build a 26-length letter-count array.
  • Turn it into a tuple (so it's hashable) and use it as a dict key.
  • Anagrams always produce the same key, so they land in the same group.
python
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        group = defaultdict(list)
        for s in strs:
            freqTable = [0] * 26
            for c in s:
                freqTable[ord(c) - ord('a')] +=1
            group[tuple(freqTable)].append(s)
        return list(group.values())
timeO(m*n)spaceO(m*n)

Majority Element

Find the element that appears more than n/2 times in nums. [2,2,1,1,1,2,2] → 2.

Boyer-Moore voting

  • Track a running count and a candidate ans.
  • count hits 0 → the current number becomes the new candidate.
  • Current number matches the candidate → count += 1, otherwise count -= 1.
  • Whatever candidate survives to the end is the majority element.
python
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        for num in nums:
            if count == 0:
                ans = num
            
            if num == ans:
                count+=1
            else:
                count-=1
 
        return ans
timeO(n)spaceO(1)

Majority Element II

Find every element that appears more than n/3 times in nums (there can be at most two). [1,1,1,3,3,2,2,2] → [1,2].

Boyer-Moore, two candidates

  • Track two candidates (num1, num2) with their own counts, since at most two numbers can pass the n/3 bar.
  • Matches an existing candidate → bump that candidate's count.
  • A count is 0 → the current number becomes that candidate.
  • Matches neither, and both counts are non-zero → decrement both.
  • Second pass: recount how often each surviving candidate actually shows up, and keep only the ones that truly exceed n/3.
python
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        n = len(nums)
        if(n<2): return nums
        num1 = num2 = -1
        count1 = count2 = 0
 
        for num in nums:
            if num == num1:
                count1 += 1
            elif num == num2:
                count2 += 1
            elif count1 == 0:
                count1 = 1
                num1 = num
            elif count2 == 0:
                count2 = 1
                num2 = num
            else:
                count1 -= 1
                count2 -= 1
 
        count1 = count2 = 0
        for num in nums:
            if num == num1:
                count1 += 1
            elif num == num2:
                count2 += 1
 
        res = []
        if count1 > n // 3:
            res.append(num1)
        if count2 > n // 3:
            res.append(num2)
 
        return res
timeO(n)spaceO(1)

Top K Frequent Elements

Return the k most frequent values in nums. nums = [1,1,1,2,2,3], k = 2 → [1,2].

1. Count, sort, take the top k

  • Count how often each number shows up, one pass.
  • Turn that into a list of [freq, num] pairs and sort it (ascending, so the most frequent end up last).
  • Pop the last k pairs off for the answer.
python
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)
 
        arr = []
        for num, freq in count.items():
            arr.append([freq, num])
        arr.sort()
 
        res = []
        while len(res) < k:
            res.append(arr.pop()[1])
        return res
timeO(n log n)spaceO(n)

2. Min-heap of size k

  • Count how often each number shows up, one pass.
  • Push (count, num) onto a min-heap. Whenever the heap grows past size k, pop the smallest.
  • What's left in the heap after the pass are the k most frequent numbers.
python
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)
 
        heap = []
        for num in count.keys():
            heapq.heappush(heap, (count[num], num))
            if len(heap) > k:
                heapq.heappop(heap)
            
        res = []
        for i in range(k):
            res.append(heapq.heappop(heap)[1])
        return res
timeO(n log k)spaceO(n)

3. Bucket sort

  • Count how often each number shows up, one pass.
  • Bucket the numbers by frequency: buckets[freq] holds every number that appears freq times.
  • Walk the buckets from highest frequency down, collecting numbers until there are k.
python
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = count.get(num, 0) + 1
        n = len(nums)
        buckets = [0] * (n+1)
        
        for num, freq in count.items():
            if buckets[freq] == 0:
                buckets[freq] = [num]
            else:
                buckets[freq].append(num)
        
        result = []
        for i in range(n, -1, -1):
            if buckets[i] != 0:
                result.extend(buckets[i])
            if len(result) == k:
                break
        
        return result
timeO(n)spaceO(n)

Product of Array Except Self

Return an array where each index holds the product of every other element. [1,2,3,4] → [24,12,8,6].

Prefix and suffix products

  • Build a pref array: pref[i] is the product of everything before index i.
  • Build a suff array: suff[i] is the product of everything after index i.
  • Multiply them together, index by index: res[i] = pref[i] * suff[i].
python
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n
        pref = [0] * n
        suff = [0] * n
 
        pref[0] = suff[n-1] = 1
        for i in range(1, n):
            pref[i] = nums[i-1] * pref[i-1]
        for i in range(n-2, -1, -1):
            suff[i] = nums[i+1] * suff[i + 1]
        for i in range(n):
            res[i] = pref[i] * suff[i]
        return res
timeO(n)spaceO(n)

Valid Sudoku

Check a 9x9 board so far: no repeated digit in any row, column, or 3x3 box. Empty cells (.) don't count.

Three passes: rows, columns, boxes

  • Check every row for a repeated digit, using a set per row.
  • Check every column for a repeated digit, using a set per column.
  • Check every 3x3 box for a repeated digit, using a set per box.
  • Any repeat that isn't . → invalid.
python
class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        
        # Rows
        for row in range(9):
            seen = set()
            for i in range(9):
                item = board[row][i]
                if item == ".":
                    continue
                if item in seen:
                    return False
                seen.add(item)
            
        # Columns
        for col in range(9):
            seen = set()
            for i in range(9):
                item = board[i][col]
                if item == ".":
                    continue
                if item in seen:
                    return False
                seen.add(item)
        
        # Boxes
        starts = [(0,0),(0,3),(0,6),
                (3,0),(3,3),(3,6),
                (6,0),(6,3),(6,6)]
        
        for i,j in starts:
            seen = set()
            for row in range(i, i+3):
                for col in range(j, j+3):
                    item = board[row][col]
                    if item in seen:
                        return False
                    elif item != '.':
                        seen.add(item)
        return True
timeO(1)spaceO(1)

Longest Consecutive Sequence

Find the length of the longest run of consecutive integers in nums, order doesn't matter. [100,4,200,1,3,2] → 4 (the run 1,2,3,4).

Only start counting from the beginning of a run

  • Put every number in a set, for O(1) lookups.
  • A number only starts a new run if num - 1 isn't in the set, nothing comes before it.
  • From there, count how far num + 1, num + 2, ... keep showing up in the set.
  • Track the longest run seen.
python
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        longest = 0
 
        for num in numSet:
            if (num-1) not in numSet:
                length = 1
                while (num+length) in numSet:
                    length += 1
                longest = max(length, longest)
        return longest
timeO(n)spaceO(n)

Best Time to Buy and Sell Stock II

Buy and sell as many times as you want (one share at a time), maximize total profit. [7,1,5,3,6,4] → 7 (buy at 1, sell at 5; buy at 3, sell at 6).

Sum every rising run

  • Scan forward to find a local low (lo).
  • Scan forward from there to find the next local high (hi).
  • Add hi - lo to the running profit.
  • Repeat until the array's exhausted.
python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        i = 0
        lo = prices[0]
        hi = prices[0]
        profit = 0
        n = len(prices)
 
        while i < n - 1:
            # look where to buy
            while i < n - 1 and prices[i] >= prices[i + 1]:
                i += 1
            lo = prices[i]
 
            # look where to sell
            while i < n - 1 and prices[i] <= prices[i + 1]:
                i += 1
            hi = prices[i]
 
            profit += hi - lo
 
        return profit
timeO(n)spaceO(1)

Subarray Sum Equals K

Count how many contiguous subarrays of nums sum to exactly k. [1,1,1], k = 2 → 2.

Prefix sum counts

  • Track a running sum (curSum) and a dict of how many times each prefix sum has shown up so far, starting with {0: 1} for the empty prefix.
  • At each step, if curSum - k has occurred before, every one of those earlier points is the start of a subarray summing to k, so add that count to the answer.
  • Record the current prefix sum in the dict, then keep going.
python
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        res = curSum = 0
        prefixSums = { 0 : 1 }
 
        for num in nums:
            curSum += num
            diff = curSum - k
 
            res += prefixSums.get(diff, 0)
            prefixSums[curSum] = 1 + prefixSums.get(curSum, 0)
 
        return res
timeO(n)spaceO(n)

Rotate Array

Rotate nums to the right by k steps, in place. [1,2,3,4,5,6,7], k = 3 → [5,6,7,1,2,3,4].

Slice and reassign

  • The last k elements (mod n, so a k bigger than the array still wraps correctly) become the new front.
  • Everything else follows behind them.
  • Assigning into nums[:] rewrites the array in place rather than rebinding nums to a new list.
python
class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums[:] = nums[-k % len(nums):] + nums[:-k % len(nums)]
timeO(n)spaceO(n)