This 5 Patterns Help You Solve Some of the Most Asked DSA Questions in Arrays

When preparing for Data Structures and Algorithms (DSA) interviews, it's crucial to master certain patterns that frequently arise in array problems. Here are five fundamental patterns, each explained with examples and pseudocode, to help you efficiently tackle some of the most common DSA questions involving arrays.

1. Two Pointers

The two-pointer technique is highly effective for solving problems that involve pairs or subarrays. It often involves using two pointers to traverse the array from different directions or within a sliding window.

Example: Two Sum in a Sorted Array

Given a sorted array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Pseudocode:

function twoSumSortedArray(nums, target):

    left = 0

    right = length(nums) - 1

    while left < right:

        sum = nums[left] + nums[right]

        if sum == target:

            return [left, right]

        elif sum < target:

            left += 1

        else:

            right -= 1

    return [-1, -1]        

2. Prefix Sum / Cumulative Sum

Prefix sum is a technique used to preprocess an array so that range queries (e.g., finding the sum of elements between two indices) can be answered quickly. It involves creating an auxiliary array where each element at index i is the sum of the elements from the start of the array to i.

Example: Range Sum Query

Given an array nums, compute the sum of elements between indices i and j (inclusive) efficiently.

Pseudocode:

function createPrefixSumArray(nums):

    prefixSum = array of size (length(nums) + 1) with all elements initialized to 0

    for i from 1 to length(nums):

        prefixSum[i] = prefixSum[i - 1] + nums[i - 1]

    return prefixSum

function rangeSumQuery(prefixSum, i, j):

    return prefixSum[j + 1] - prefixSum[i]        

3. Kadane’s Algorithm

Kadane's Algorithm is a dynamic programming approach to find the maximum sum subarray in an array. It works by maintaining a running maximum sum and updating it as it iterates through the array.

Example: Maximum Subarray Sum

Find the contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Pseudocode:

function maxSubArray(nums):

    maxCurrent = nums[0]

    maxGlobal = nums[0]

    for i from 1 to length(nums):

        maxCurrent = max(nums[i], maxCurrent + nums[i])

        if maxCurrent > maxGlobal:

            maxGlobal = maxCurrent

    return maxGlobal        

4. Sorting

Sorting an array can simplify many problems, especially those involving comparisons, searching for pairs, or finding sequences. Once the array is sorted, it becomes easier to apply binary search or two-pointer techniques.

Example: Merging Intervals

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals.

Pseudocode:

function mergeIntervals(intervals):

    if intervals is empty:

        return intervals

    sort intervals by start time

    merged = []

    for interval in intervals:

        if merged is empty or merged[-1][1] < interval[0]:

            merged.append(interval)

        else:

            merged[-1][1] = max(merged[-1][1], interval[1])

    return merged        

5. Hashing

Hashing involves using hash maps or hash sets to achieve constant-time lookups. This technique is particularly useful for problems that require checking the existence of an element or counting frequencies.

Example: Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Pseudocode:

function containsDuplicate(nums):

    seen = set()

    for num in nums:

        if num in seen:

            return True

        seen.add(num)

    return False        

Conclusion

These five patterns—Two Pointers, Prefix Sum, Kadane’s Algorithm, Sorting, and Hashing—are fundamental tools for solving array problems in DSA interviews. By mastering these techniques and understanding when to apply them, you'll be well-prepared to tackle a wide range of questions and improve your problem-solving efficiency. Practice these patterns with various problems to gain confidence and enhance your interview performance.