FAANG Coding Interview Mastery: Arrays & Strings Core Patterns

Arrays and strings account for over 40% of FAANG (Facebook/Meta, Apple, Amazon, Netflix, Google) coding interview questions. This guide covers 6 essential patterns you must master, complete with working Python code and in-depth analysis.

1. Two Pointers Pattern

Concept and When to Use It

The Two Pointers pattern uses two indices to traverse a sorted array or string in linear time, eliminating the need for nested loops.

Use when:

Finding pairs in a sorted array that satisfy a condition
Comparing elements from both ends of an array
Removing duplicates or partitioning in-place

Core insight: Reduces O(n^2) brute force to O(n).

Problem 1: Two Sum II (LeetCode 167)

Given a sorted array, find two numbers that add up to the target.

def twoSum(numbers: list[int], target: int) -> list[int]:
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return []

# Example
# Input: numbers = [2,7,11,15], target = 9
# Output: [1,2]

Time Complexity: O(n) — each pointer moves at most n steps total Space Complexity: O(1) — no extra space needed

FAANG Tip: For unsorted arrays, present a HashMap O(n) solution first, then explain why Two Pointers is more space-efficient on sorted input.

Problem 2: 3Sum (LeetCode 15)

Find all unique triplets in the array that sum to zero.

def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        # Skip duplicates for the first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, len(nums) - 1

        while left < right:
            total = nums[i] + nums[left] + nums[right]

            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                # Skip duplicates
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

# Example
# Input: nums = [-1, 0, 1, 2, -1, -4]
# Output: [[-1, -1, 2], [-1, 0, 1]]

Time Complexity: O(n^2) — sort O(n log n) plus double loop O(n^2) Space Complexity: O(1) to O(n) depending on sort algorithm

FAANG Tip: A frequent Meta interview question. Don't miss the duplicate-skipping logic — interviewers often probe for it.

Problem 3: Container With Most Water (LeetCode 11)

Given a height array, find the maximum area of water that can be contained.

def maxArea(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        current_water = width * min(height[left], height[right])
        max_water = max(max_water, current_water)

        # Move the pointer at the shorter wall (seeking a taller one)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

# Example
# Input: height = [1,8,6,2,5,4,8,3,7]
# Output: 49

Time Complexity: O(n) Space Complexity: O(1)

Why is this optimal? Moving the taller wall would only decrease the width while never increasing the limiting height — so it can never yield a larger area.

Problem 4: Trapping Rain Water (LeetCode 42)

Compute how much rainwater can be trapped between the bars.

def trap(height: list[int]) -> int:
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0

    while left < right:
        if left_max <= right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]

    return water

# Example
# Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
# Output: 6

Time Complexity: O(n) Space Complexity: O(1) — no prefix max arrays needed

FAANG Tip: A staple at Google and Amazon. Know both the DP approach (O(n) space) and this Two Pointers approach, and be ready to explain why they are equivalent.

2. Sliding Window Pattern

Concept

The Sliding Window pattern finds optimal subarrays or substrings by maintaining a window that expands and contracts as it slides through the input.

Fixed Window: Window size is constant Variable Window: Window size adjusts based on a constraint

Problem 5: Longest Substring Without Repeating Characters (LeetCode 3)

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1

        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

# Optimized version using a HashMap
def lengthOfLongestSubstringOptimized(s: str) -> int:
    char_index = {}
    left = 0
    max_length = 0

    for right, char in enumerate(s):
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1

        char_index[char] = right
        max_length = max(max_length, right - left + 1)

    return max_length

# Example
# Input: "abcabcbb"
# Output: 3 ("abc")

Time Complexity: O(n) Space Complexity: O(min(n, charset_size))

Problem 6: Minimum Window Substring (LeetCode 76)

Find the smallest window in s that contains all characters of t.

from collections import Counter

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""

    need = Counter(t)
    missing = len(t)  # Characters still needed

    best_start = 0
    best_end = float('inf')
    left = 0

    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1

        if missing == 0:
            # Shrink from the left
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1

            if right - left < best_end - best_start:
                best_start = left
                best_end = right

            # Slide the window forward
            need[s[left]] += 1
            missing += 1
            left += 1

    if best_end == float('inf'):
        return ""
    return s[best_start:best_end + 1]

# Example
# Input: s = "ADOBECODEBANC", t = "ABC"
# Output: "BANC"

Time Complexity: O(|s| + |t|) Space Complexity: O(|s| + |t|)

Problem 7: Sliding Window Maximum (LeetCode 239)

Return the maximum of each sliding window of size k.

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()  # Stores indices in decreasing order of values
    result = []

    for i, num in enumerate(nums):
        # Remove indices outside the window
        if dq and dq[0] < i - k + 1:
            dq.popleft()

        # Remove indices with smaller values (they can never be the max)
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        # Start recording once the first window is full
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

# Example
# Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
# Output: [3,3,5,5,6,7]

Time Complexity: O(n) — each element is added/removed from deque at most once Space Complexity: O(k)

Problem 8: Fruit Into Baskets (LeetCode 904)

Find the maximum number of fruits you can collect if you can only carry at most 2 types.

from collections import defaultdict

def totalFruit(fruits: list[int]) -> int:
    basket = defaultdict(int)
    left = 0
    max_fruits = 0

    for right, fruit in enumerate(fruits):
        basket[fruit] += 1

        # Shrink window when we have more than 2 fruit types
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1

        max_fruits = max(max_fruits, right - left + 1)

    return max_fruits

# Example
# Input: fruits = [1,2,1,2,3]
# Output: 4 ([1,2,1,2])

Time Complexity: O(n) Space Complexity: O(1) — at most 3 fruit types stored at once

3. Binary Search Pattern

Concept

Binary Search finds elements in a sorted array in O(log n) time. FAANG interviews frequently test non-standard variants.

Standard Binary Search Template:

def binarySearch(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2  # Avoids integer overflow

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Problem 9: Search in Rotated Sorted Array (LeetCode 33)

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

# Example
# Input: nums = [4,5,6,7,0,1,2], target = 0
# Output: 4

Time Complexity: O(log n) Space Complexity: O(1)

Problem 10: Find Minimum in Rotated Sorted Array (LeetCode 153)

def findMin(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:
            left = mid + 1  # Min is in the right half
        else:
            right = mid     # Mid could be the minimum

    return nums[left]

# Example
# Input: nums = [3,4,5,1,2]
# Output: 1

Time Complexity: O(log n) Space Complexity: O(1)

Problem 11: Median of Two Sorted Arrays (LeetCode 4) — Hard

def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
    # Ensure nums1 is the smaller array
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    half_len = (m + n + 1) // 2

    left, right = 0, m

    while left <= right:
        i = (left + right) // 2  # Partition index in nums1
        j = half_len - i          # Partition index in nums2

        if i < m and nums1[i] < nums2[j - 1]:
            left = i + 1
        elif i > 0 and nums1[i - 1] > nums2[j]:
            right = i - 1
        else:
            # Correct partition found
            if i == 0:
                max_left = nums2[j - 1]
            elif j == 0:
                max_left = nums1[i - 1]
            else:
                max_left = max(nums1[i - 1], nums2[j - 1])

            if (m + n) % 2 == 1:
                return float(max_left)

            if i == m:
                min_right = nums2[j]
            elif j == n:
                min_right = nums1[i]
            else:
                min_right = min(nums1[i], nums2[j])

            return (max_left + min_right) / 2.0

# Example
# Input: nums1 = [1,3], nums2 = [2]
# Output: 2.0

Time Complexity: O(log(min(m, n))) Space Complexity: O(1)

Problem 12: Search a 2D Matrix (LeetCode 74)

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    if not matrix or not matrix[0]:
        return False

    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1

    while left <= right:
        mid = left + (right - left) // 2
        # Map 1D index to 2D coordinates
        mid_val = matrix[mid // cols][mid % cols]

        if mid_val == target:
            return True
        elif mid_val < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

# Example
# Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
# Output: True

Time Complexity: O(log(m*n)) Space Complexity: O(1)

4. Prefix Sum & Hash Map Pattern

Concept

Prefix Sum precomputes cumulative sums so that range sum queries run in O(1). Combined with a HashMap, it finds subarrays satisfying specific conditions efficiently.

Problem 13: Subarray Sum Equals K (LeetCode 560)

Count the number of contiguous subarrays whose sum equals k.

from collections import defaultdict

def subarraySum(nums: list[int], k: int) -> int:
    prefix_sum_count = defaultdict(int)
    prefix_sum_count[0] = 1  # Empty prefix has sum 0

    current_sum = 0
    count = 0

    for num in nums:
        current_sum += num
        # If (current_sum - k) was seen before, those subarrays sum to k
        count += prefix_sum_count[current_sum - k]
        prefix_sum_count[current_sum] += 1

    return count

# Example
# Input: nums = [1,1,1], k = 2
# Output: 2

Time Complexity: O(n) Space Complexity: O(n)

Problem 14: Longest Consecutive Sequence (LeetCode 128)

Find the length of the longest consecutive sequence in O(n) time.

def longestConsecutive(nums: list[int]) -> int:
    num_set = set(nums)
    max_length = 0

    for num in num_set:
        # Only start a sequence from its lowest element
        if num - 1 not in num_set:
            current = num
            length = 1

            while current + 1 in num_set:
                current += 1
                length += 1

            max_length = max(max_length, length)

    return max_length

# Example
# Input: nums = [100,4,200,1,3,2]
# Output: 4 ([1,2,3,4])

Time Complexity: O(n) — each number is visited at most twice Space Complexity: O(n)

Problem 15: Group Anagrams (LeetCode 49)

Group strings that are anagrams of each other.

from collections import defaultdict

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    anagram_map = defaultdict(list)

    for s in strs:
        key = tuple(sorted(s))
        anagram_map[key].append(s)

    return list(anagram_map.values())

# Optimized version using character count as key
def groupAnagramsOptimized(strs: list[str]) -> list[list[str]]:
    anagram_map = defaultdict(list)

    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        anagram_map[tuple(count)].append(s)

    return list(anagram_map.values())

# Example
# Input: strs = ["eat","tea","tan","ate","nat","bat"]
# Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Time Complexity: O(n _ k) — n strings, k is max string length Space Complexity: O(n _ k)

Problem 16: Top K Frequent Elements (LeetCode 347)

from collections import Counter
import heapq

def topKFrequent(nums: list[int], k: int) -> list[int]:
    # Approach 1: Heap — O(n log k)
    count = Counter(nums)
    return heapq.nlargest(k, count.keys(), key=count.get)

def topKFrequentBucketSort(nums: list[int], k: int) -> list[int]:
    # Approach 2: Bucket Sort — O(n)
    count = Counter(nums)

    # Index = frequency, value = list of numbers with that frequency
    bucket = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        bucket[freq].append(num)

    result = []
    for freq in range(len(bucket) - 1, 0, -1):
        for num in bucket[freq]:
            result.append(num)
            if len(result) == k:
                return result

    return result

# Example
# Input: nums = [1,1,1,2,2,3], k = 2
# Output: [1,2]

Time Complexity: O(n) with Bucket Sort Space Complexity: O(n)

5. FAANG Company-Specific Trends

Google

Google interviews are Array and String manipulation heavy.

Frequent: Two Sum variants, string parsing, 2D array traversal
Key skills: Edge case handling, code clarity and readability
Example problems: Longest Substring with At Most K Distinct Characters, Minimum Number of Arrows to Burst Balloons

Meta (Facebook)

Meta favors Sliding Window and Two Pointer patterns.

Frequent: 3Sum, Valid Palindrome II, Move Zeroes
Key skills: Explaining optimization rationale, concise code
Example problems: Subarray Product Less Than K, Permutation in String

Amazon

Amazon leans toward Hash Table and Sorting based problems.

Frequent: Two Sum, Group Anagrams, Top K Frequent
Key skills: Practical solutions, tying to Leadership Principles
Example problems: K Closest Points to Origin, Sort Colors

Microsoft

Microsoft asks Binary Search variants and array manipulation.

Frequent: Find Peak Element, Search a 2D Matrix
Key skills: Rigorous edge case coverage, bug-free code
Example problems: Spiral Matrix, Rotate Image

6. Interview Strategy

Problem-Solving Framework (45 Minutes)

Step 1 — Clarify (5 minutes)

Always ask the interviewer:

Input range and types (can values be negative? duplicates allowed?)
Output format (indices? values? count?)
Edge cases (empty array, single element, all same value)
Optimization target (time vs. space)

Step 2 — Brute Force (5 minutes)

State a naive O(n^2) or O(n^3) solution. This establishes a baseline.

Step 3 — Optimize (10 minutes)

Identify the pattern: Two Pointers? Sliding Window? Hash Map? Discuss trade-offs with the interviewer before coding.

Step 4 — Code (15 minutes)

Write clean code with meaningful variable names:

def solve(nums, target):
    # Initialize two pointers
    left, right = 0, len(nums) - 1

    while left < right:
        # ... logic
        pass

Step 5 — Test (10 minutes)

Walk through your own test cases:

Normal case
Edge cases (empty array, length 1)
Worst case (all duplicates, reverse sorted)

Edge Case Checklist

Always verify these for array/string problems:

Empty input ([], "")
Single element ([5], "a")
All identical values ([3,3,3,3])
Already sorted input
Reverse sorted input
Integer overflow potential
Negative numbers

Time Allocation Table

Phase	Time	Key Focus
Clarify	5 min	Ask questions, nail requirements
Brute Force	5 min	Establish baseline solution
Optimize	10 min	Identify pattern, improve complexity
Coding	15 min	Clean, bug-free implementation
Testing	10 min	Trace through, catch edge cases

7. Practice Quiz

Quiz 1: Remove Duplicates from Sorted Array with Two Pointers

Given sorted array nums = [0,0,1,1,1,2,2,3,3,4], remove duplicates in-place using O(1) extra space and return the count of unique elements.

Answer: 5 (array becomes [0,1,2,3,4,...])

Explanation: Use slow and fast pointers. The slow pointer tracks the next write position. When nums[fast] != nums[slow], increment slow and overwrite.

def removeDuplicates(nums):
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

Quiz 2: Max Consecutive Ones with One Flip

Binary array nums = [1,1,0,0,1,1,1,0,1]. You may flip at most k=1 zeros to ones. Find the maximum length of a contiguous subarray of ones.

Answer: 6

Explanation: Variable Sliding Window. Track the count of zeros in the window; shrink from the left when zeros exceed k.

def longestOnes(nums, k):
    left = 0
    zeros = 0
    max_len = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

Quiz 3: Binary Search for First and Last Position

Sorted array nums = [5,7,7,8,8,10], target = 8. Find the first and last index.

Answer: [3, 4]

Explanation: Run Binary Search twice — once biased left (continue searching left after finding target), once biased right.

def searchRange(nums, target):
    def findLeft(nums, target):
        left, right, idx = 0, len(nums) - 1, -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                idx = mid
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return idx

    def findRight(nums, target):
        left, right, idx = 0, len(nums) - 1, -1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                idx = mid
                left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return idx

    return [findLeft(nums, target), findRight(nums, target)]

Quiz 4: Count Subarrays with Zero Sum using Prefix Sum

Array [1, -1, 1, -1, 1] — how many contiguous subarrays have sum equal to 0?

Answer: 4

Explanation: Use Prefix Sum + HashMap. Every time the same prefix sum appears again, all subarrays between those two positions have sum 0. Count with count += prefix_sum_count[current_sum - k].

from collections import defaultdict
def subarraySum(nums, k=0):
    prefix_sum_count = defaultdict(int)
    prefix_sum_count[0] = 1
    current_sum = 0
    count = 0
    for num in nums:
        current_sum += num
        count += prefix_sum_count[current_sum - k]
        prefix_sum_count[current_sum] += 1
    return count
# Result: 4

Quiz 5: Product of Array Except Self

Array nums = [1,2,3,4]. Return an array where each element is the product of all other elements. No division allowed. O(n) time, O(1) extra space.

Answer: [24, 12, 8, 6]

Explanation: Two passes — first accumulate left products into the result array, then multiply by right products in a second pass from the right.

def productExceptSelf(nums):
    n = len(nums)
    result = [1] * n

    # Pass 1: left products
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # Pass 2: multiply by right products
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

Conclusion

Arrays and strings are the bedrock of FAANG coding interviews. Mastering these 6 patterns lets you recognize most problems instantly and approach them with an optimal strategy.

Next steps:

Solve 20 problems per pattern on LeetCode
Practice under a 45-minute timer
Code review: compare your solution with top-voted answers
Flip the script: try creating your own problem variants

The next guide in this series covers Trees and Graphs patterns.