Afasari

(Re)Start Learning Data Structure and Algorithm - Part 3, Array

Roadmap

Based on https://neetcode.io/roadmap, there are a lot of data structure and algorithm including their pattern to solve. The first topic is about array and hashing and then continue to stack until cover all of leetcode 75 or neetcode 150 or neetcode 250

Here is the roadmap

flowchart TD

A[Array & Hashing] --> B[Two Pointers]
A --> C[Stack]
B --> D[Binary Search]
B --> E[Sliding Window]
B --> F[Linked List]
D --> G[Trees]
F --> G
G --> H[Tries]
G --> I[Heap/Priority Queue]
G --> J[Backtracking]
I --> K[Intervals]
I --> L[Greedy]
I --> M[Advanced Graphic]
J --> O[Graphs]
J --> P[1D DP]
O --> M
O --> S[Math & Geometery]
O --> Q[2D DP]
P --> Q
P --> R[Bit Manipulation]
R --> S

Another great roadmap to follow is from algomonster

data structures algorithms problem-solving techniques
arrays sorting two pointers
linked lists searching sliding window
stacks linear search prefix sum
queues binary search fast and slow pointers
hash tables bit manipulation divide and conquer
trees tree traversal greedy
binary search trees in order recursion
heaps pre order backracking
graphs post order dynamic programming
trie graph algorithms top ‘K’ elements
union find dfs/bfs  
  topological sort  
  shortest path  
  minimum spanning tree  

Let’s start from the first topic, Array and Hashing

Array & Hashing

Problem Difficulty
Contains Duplicate Easy
Valid Anagram Easy
Two Sum Easy
Group Anagrams Medium
Top K Frequent Elements Medium
Encode and Decode Strings Medium
Product of Array Except Self Medium
Longest Consecutive Sequence Medium

LeetCode 217: Contains Duplicate

  1. Title & Problem Goal
  1. Analysis & Constraints
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Brute Force Compare every pair using nested loops. 𝑂(𝑛^2) 𝑂(1) Too slow for large inputs.
Sorting Sort the array and check if nums[i] == nums[i+1]. 𝑂(𝑛log𝑛) 𝑂(1)

or

𝑂(𝑛)		 Good if memory is extremely limited.
Hash Set Store visited numbers in a set; if a number is already in the set, return true. 𝑂(𝑛) 𝑂(𝑛) Fastest. Standard choice for modern hardware.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: The Hash Set (map in Go) provides 𝑂(1) average time complexity for both insertions and lookups. This allows us to solve the problem in a single linear pass.

func containsDuplicate(nums []int) bool {
    // 1. Initialize a map to act as a Set
    // We use struct{} because it occupies zero bytes of memory
    visited := make(map[int]struct{})

    for _, n := range nums {
        // 2. Check if the number has been seen before
        if _, exists := visited[n]; exists {
            return true
        }
        // 3. Mark the number as visited
        visited[n] = struct{}{}
    }

    // 4. If the loop finishes, no duplicates were found
    return false
}
  1. Reflection / Mistake Log

LeetCode 242: Valid Anagram

  1. Title & Problem Goal
  1. Analysis & Constraints
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Sorting Sort both strings; compare if sortedS == sortedT. 𝑂(𝑛log𝑛) 𝑂(1) or 𝑂(𝑛) Very easy to write; slower for large strings.
Hash Map Count chars in s (+), then in t (-). Check if all counts are 0. 𝑂(𝑛) 𝑂(𝑘) (𝑘=26) Faster; works for Unicode (if using a Map).
Frequency Array Use an int[26] to track counts. 𝑂(𝑛) 𝑂(1) Most efficient for lowercase English letters.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: It uses a single pass to build counts and a fixed-size array. This avoids the overhead of a dynamic Hash Map and stays at 𝑂(𝑛) time.

func isAnagram(s string, t string) bool {
    // 1. Length check is the fastest way to exit
    if len(s) != len(t) {
        return false
    }

    // 2. Use a fixed-size array (alphabet)
    // Space: O(1) because size 26 never changes
    alphabet := [26]int{}

    // 3. Single loop: increment for s, decrement for t
    // Time: O(n)
    for i := 0; i < len(s); i++ {
        alphabet[s[i]-'a']++
        alphabet[t[i]-'a']--
    }

    // 4. If all counts are zero, it's an anagram
    for _, count := range alphabet {
        if count != 0 {
            return false
        }
    }

    return true
}
  1. Reflection / Mistake Log

LeetCode 1: Two Sum

  1. Title & Problem Goal
  1. Analysis & Constraints
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Brute Force Nested loops check every pair (𝑖,𝑗). 𝑂(𝑛^2) 𝑂(1) Simple to implement but slow for large 𝑛.
Two-Pass Hash Table First pass builds map (value → index); second pass looks for complement. 𝑂(𝑛) 𝑂(𝑛) Fast but requires two iterations over the data.
One-Pass Hash Table Check for complement while building the map in a single pass. 𝑂(𝑛) 𝑂(𝑛) Most efficient. Finds the pair in one traversal.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative Cases (Validation):

  1. Optimal Code & Why (Golang)

Why this is optimal: The One-Pass Hash Table ensures we only traverse the array once (𝑂(𝑛)) and perform lookups in constant time (𝑂(1)) on average.

func twoSum(nums []int, target int) []int {
    // 1. Create a map to store seen values and their indices
    // Key: Number value, Value: Index in the original array
    prevMap := make(map[int]int)

    for i, num := range nums {
        // 2. Calculate the required complement
        complement := target - num

        // 3. Check if complement was already encountered
        if index, exists := prevMap[complement]; exists {
            return []int{index, i}
        }

        // 4. Otherwise, store current number and its index
        prevMap[num] = i
    }

    return nil
}
  1. Reflection / Mistake Log

LeetCode 49: Group Anagrams

 1. Title & Problem Goal

  1. Analysis & Constraints
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Brute Force Compare every pair of strings to see if they are anagrams. 𝑂(𝑁^2×𝐾) 𝑂(1) Too slow for 𝑁=10^4.
Sorting Sort each string alphabetically and use the sorted string as a Hash Map key. 𝑂(𝑁×𝐾log𝐾) 𝑂(𝑁×𝐾) Simple to implement; slightly slower due to sorting.
Categorize by Count Use a 26-element array to count char frequencies; use the array/tuple as a Hash Map key. 𝑂(𝑁×𝐾) 𝑂(𝑁×𝐾) Most optimized as it avoids the 𝑂(𝐾log𝐾) sort per word.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative/Special Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: This approach uses a fixed-size array ([26]int) to represent the character frequency of each word. Since arrays in Go are comparable, they can be used directly as map keys. This skips the 𝑂(𝐾log𝐾) sorting cost entirely.

func groupAnagrams(strs []string) [][]string {
    // 1. Map to group words by their character count signature
    // Key: [26]int (count of each char a-z), Value: slice of original words
    groups := make(map[[26]int][]string)

    for _, s := range strs {
        // 2. Generate the "signature" for the current word
        var count [26]int
        for i := 0; i < len(s); i++ {
            count[s[i]-'a']++
        }

        // 3. Group words sharing the same signature
        groups[count] = append(groups[count], s)
    }

    // 4. Collect all groups into a list of lists
    result := make([][]string, 0, len(groups))
    for _, group := range groups {
        result = append(result, group)
    }

    return result
}
  1. Reflection / Mistake Log

LeetCode 347: Top K Frequent Elements

  1. Title & Problem Goal
  1. Analysis & Constraints
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Sorting Count frequencies, then sort the list of unique elements by frequency. 𝑂(𝑛log𝑛) 𝑂(𝑛) Simple but doesn’t meet the “better than 𝑂(𝑛log𝑛)” requirement.
Min-Heap Count frequencies, push into a heap of size 𝑘. Pop the smallest if size exceeds 𝑘. 𝑂(𝑛log𝑘) 𝑂(𝑛) Good if 𝑘 is much smaller than 𝑛.
Bucket Sort Map values to frequencies, then use frequencies as indices in an array of lists. 𝑂(𝑛) 𝑂(𝑛) Most optimized. Linear time regardless of 𝑘.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative/Special Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: This is the Bucket Sort approach. By using the frequency as an index, we avoid any sorting or heap overhead. We simply iterate backward from the highest possible frequency until we collect 𝑘 elements.

func topKFrequent(nums []int, k int) []int {
    // 1. Count frequencies: O(n)
    counts := make(map[int]int)
    for _, num := range nums {
        counts[num]++
    }

    // 2. Create buckets where index = frequency: O(n)
    // bucket[i] contains all numbers that appear i times
    buckets := make([][]int, len(nums)+1)
    for num, freq := range counts {
        buckets[freq] = append(buckets[freq], num)
    }

    // 3. Iterate backwards from highest frequency: O(n)
    result := make([]int, 0, k)
    for i := len(buckets) - 1; i >= 0 && len(result) < k; i-- {
        if len(buckets[i]) > 0 {
            result = append(result, buckets[i]...)
        }
    }

    // Return exactly k elements (in case bucket contained more than needed)
    return result[:k]
}
  1. Reflection / Mistake Log

LeetCode 271: Encode and Decode Strings

  1. Title & Problem Goal
  1. Analysis & Constraints
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Non-ASCII Delimiter Use a character outside the standard 256 range. 𝑂(𝑀) 𝑂(𝑀) Simple, but fails if the environment strictly requires ASCII.
Escaping Choose a delimiter and “escape” it whenever it appears in the input. 𝑂(𝑀) 𝑂(𝑀) Conceptually like CSV; logic for nested escaping can get complex.
Length Prefix + Delimiter Prefix each string with its length + #. To decode, read the length, skip #, and take 𝐿

characters.		 𝑂(𝑀) 𝑂(𝑀) Most Robust. Guaranteed to work regardless of string content.
Chunked Encoding Use a fixed 4-byte string for length (e.g., 0005hello). 𝑂(𝑀) 𝑂(𝑀) Very fast decoding; mimics HTTP/1.1 chunked transfer.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: The length + delimiter pattern is the gold standard for serialization (like Protobuf or gRPC) because it avoids scanning the entire string for “escaped” characters during decoding. You jump directly to the next word based on its known length.

type Codec struct{}

// Encode converts a list of strings to a single string
func (c *Codec) Encode(strs []string) string {
    var encoded strings.Builder
    for _, s := range strs {
        // Format: [length]#[string]
        encoded.WriteString(strconv.Itoa(len(s)))
        encoded.WriteByte('#')
        encoded.WriteString(s)
    }
    return encoded.String()
}

// Decode converts a single string back to a list of strings
func (c *Codec) Decode(s string) []string {
    var res []string
    i := 0
    for i < len(s) {
        // 1. Find the delimiter to determine where the length ends
        j := i
        for s[j] != '#' {
            j++
        }

        // 2. Parse the length
        length, _ := strconv.Atoi(s[i:j])

        // 3. Extract the string of the given length
        start := j + 1
        end := start + length
        res = append(res, s[start:end])

        // 4. Move pointer to the start of the next length prefix
        i = end
    }
    return res
}
  1. Reflection / Mistake Log

LeetCode 238: Product of Array Except Self

  1. Title & Problem Goal
  1. Analysis & Constraints
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Brute Force Nested loops: for each i, multiply all other elements. 𝑂(𝑛2) 𝑂(1) Simple but too slow for 𝑛=10^5.
Division Multiply all, then divide total / nums[i]. 𝑂(𝑛) 𝑂(1) Forbidden by problem; fails if array has zeros.
Prefix & Suffix Arrays Precalculate prefix and suffix product arrays and multiply them. 𝑂(𝑛) 𝑂(𝑛) Clean logic; uses extra 𝑂(𝑛) memory for two arrays.
Two-Pass (Space Optimized) Calculate prefixes into the result array, then multiply suffixes using a single variable. 𝑂(𝑛) 𝑂(1) Most Optimized. Meets all constraints.
  1. Testing Strategy

Standard Cases:

Edge Cases (Zeros):

Boundaries & Negatives:

  1. Optimal Code & Why (Golang)

Why this is optimal: This approach avoids extra arrays by storing prefix products directly in the ans array during the first pass. A second backward pass uses a single integer variable (suffix) to maintain the running product from the right, satisfying the 𝑂(1) extra space requirement.

func productExceptSelf(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)

    // 1. Prefix pass: ans[i] stores product of all elements to the left
    ans[0] = 1
    for i := 1; i < n; i++ {
        ans[i] = ans[i-1] * nums[i-1]
    }

    // 2. Suffix pass: multiply prefix with running suffix product
    suffix := 1
    for i := n - 1; i >= 0; i-- {
        ans[i] *= suffix
        suffix *= nums[i]
    }

    return ans
}
  1. Reflection / Mistake Log

LeetCode 128: Longest Consecutive Sequence

  1. Title & Problem Goal
  1. Analysis & Constraints (2025 Data)
  1. Approaches Comparison Table
Approach Logic Time Complexity Space Complexity Pros/Cons
Brute Force For each number, search for 𝑛+1,𝑛+2… linearly. 𝑂(𝑛^3) or 𝑂(𝑛^2) 𝑂(1) Extremely slow.
Sorting Sort the array and iterate to find the longest streak. 𝑂(𝑛log𝑛) 𝑂(1) or 𝑂(𝑛) Easy to implement; violates 𝑂(𝑛) requirement.
Hash Set (Optimal) Store all numbers in a Set. Only start counting if num - 1 is not in the set. 𝑂(𝑛) 𝑂(𝑛) Most Optimized. Each number is visited at most twice.
  1. Testing Strategy

Standard Cases:

Edge Cases (Boundaries):

Negative Cases:

  1. Optimal Code & Why (Golang)

Why this is optimal: By checking !set[n-1], we ensure that we only start the inner while loop for the first element of any sequence. Even though there is a nested loop, each element is touched a constant number of times across the entire runtime, maintaining 𝑂(𝑛).

func longestConsecutive(nums []int) int {
 if len(nums) == 0 {
  return 0
 }

 // 1. Create a Set (map in Go) for O(1) lookups
 set := make(map[int]struct{})
 for _, n := range nums {
  set[n] = struct{}{}
 }

 longest := 0

 // 2. Iterate through the set (to skip duplicates automatically)
 for n := range set {
  // 3. Check if 'n' is the START of a sequence
  // If n-1 exists, 'n' is NOT the start, so we skip it
  if _, hasLeft := set[n-1]; !hasLeft {
   currentNum := n
   currentStreak := 1

   // 4. Count how far the sequence goes
   for {
    if _, hasRight := set[currentNum+1]; hasRight {
     currentNum++
     currentStreak++
    } else {
     break
    }
   }

   // 5. Update global maximum
   if currentStreak > longest {
    longest = currentStreak
   }
  }
 }

 return longest
}
  1. Reflection / Mistake Log

This post is part of a series: (Re)Start Learning DSA

  1. (Re)Start Learning Data Structure and Algorithm - Part 0, Introduction
  2. (Re)Start Learning Data Structure and Algorithm - Part 1, Complexities
  3. (Re)Start Learning Data Structure and Algorithm - Part 2, Mathematics
  4. (Re)Start Learning Data Structure and Algorithm - Part 3, Array (this post)
  5. (Re)Start Learning Data Structure and Algorithm - Part 4, Two Pointers
  6. (Re)Start Learning Data Structure and Algorithm - Part 5, Stack