all topics

Arrays & Hashing

1929. 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)

217. 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)

242. 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)

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]:
        prevMap = {}
 
        for i,n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
 
            prevMap[n] = i
timeO(n)spaceO(n)