Pattern #2

Arrays

Important interview questions, thinking patterns, and rules for solving array problems in Go.

Must Solve

17 core questions — solve these first.

  1. 1.Two Sum
    easy
  2. 2.Contains Duplicate
    easy
  3. 3.Best Time to Buy and Sell Stock
    easy
  4. 4.Maximum Subarray
    medium
  5. 5.Move Zeroes
    easy
  6. 6.Remove Duplicates from Sorted Array
    easy
  7. 7.Merge Sorted Array
    easy
  8. 8.Majority Element
    easy
  9. 9.Missing Number
    easy
  10. 10.Rotate Array
    medium
  11. 11.Product of Array Except Self
    medium
  12. 12.3Sum
    medium
  13. 13.Container With Most Water
    medium
  14. 14.Longest Consecutive Sequence
    medium
  15. 15.Subarray Sum Equals K
    medium
  16. 16.Maximum Product Subarray
    medium
  17. 17.Trapping Rain Water
    hard

Also Important

9 more questions worth practicing.

  1. 18.Find All Numbers Disappeared in an Array
    easy
  2. 19.Find the Duplicate Number
    medium
  3. 20.Sort Colors
    medium
  4. 21.Next Permutation
    medium
  5. 22.Set Matrix Zeroes
    medium
  6. 23.Spiral Matrix
    medium
  7. 24.Merge Intervals
    medium
  8. 25.Insert Interval
    medium
  9. 26.First Missing Positive
    hard

How to Think

  1. Need pair?Hash Map / Two Pointers
  2. Array is sorted?Two Pointers / Binary Search
  3. Need duplicate/frequency?Hash Map / Hash Set
  4. Need maximum subarray sum?Kadane's Algorithm
  5. Need continuous subarray?Sliding Window / Prefix Sum
  6. Need sum = K?Prefix Sum + Hash Map
  7. Need modify without extra memory?In-place / Two Pointers
  8. Need triplet?Sort + Two Pointers
  9. Need max/min while scanning?Keep running max/min
  10. Need nearest left/right bigger/smaller?Stack

Go Quick Reference

Two Sum (Hash Map)

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, v := range nums {
        if j, ok := m[target-v]; ok {
            return []int{j, i}
        }
        m[v] = i
    }
    return nil
}

👉 Time: O(n) | Space: O(n)

Kadane's — Maximum Subarray

func maxSubArray(nums []int) int {
    maxSum, curSum := nums[0], nums[0]
    for _, v := range nums[1:] {
        if curSum < 0 {
            curSum = 0
        }
        curSum += v
        if curSum > maxSum {
            maxSum = curSum
        }
    }
    return maxSum
}

👉 Time: O(n) | Space: O(1)

3Sum (Sort + Two Pointers)

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var res [][]int
    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] { continue }
        lo, hi := i+1, len(nums)-1
        for lo < hi {
            sum := nums[i] + nums[lo] + nums[hi]
            if sum == 0 {
                res = append(res, []int{nums[i], nums[lo], nums[hi]})
                for lo < hi && nums[lo] == nums[lo+1] { lo++ }
                for lo < hi && nums[hi] == nums[hi-1] { hi-- }
                lo++; hi--
            } else if sum < 0 { lo++ } else { hi-- }
        }
    }
    return res
}

👉 Time: O(n²) | Space: O(1)

Interview Rules

  1. 1. First understand: subarray or subsequence?
  2. 2. Check if array is sorted.
  3. 3. Check if duplicates exist.
  4. 4. Ask if extra memory is allowed.
  5. 5. Try to improve O(n²) to O(n) or O(n log n).

Always Test These Edge Cases

Empty array → []

One element → [5]

Duplicates → [1, 1, 1]

Negative numbers → [-3, -1, 0]

Already sorted → [1, 2, 3, 4]

💡 Arrays are the most common interview topic. Master these 26 problems and you cover 80% of array questions.