DSA Interview Notes: Array [Part 1]

Array is a fundamental data structure which is used to store elements of same data type. In an array, elements are stored in contiguous memory location.

Time complexity of best algorithm to sort the array is O(nlogn)

Index plays a very important role in problems related to array. Depending on the problem, you need to use additional variables which will act as an index in your input array.

Two pointer approach

It is a technique used for efficiently solving problems related to arrays and linked lists. The basic idea is to use two pointers that traverses the array or list in a way that will help identify a solution, subarray or some property of data efficiently.

When can you apply it?
There needs to be a certain relation in the input and the output which is required.

Some common scenarios where you can apply two-pointer approach is:

No	Problem	Description	Approach
1	Two sum	Finding a pair in sorted array	Create left and right pointers initialized to 0 and n-1. Move left+1 if target is higher and right-1 otherwise. Terminate the loop if the answer is found.
2	Remove duplicates from sorted array	Remove duplicates in-place and return length	Keep one pointer to track the index that denotes length of unique elements and other one to iterate all values.
3	Move Zeroes	Move all zeroes to the end	Keep one pointer to track the index of non-negative integer and other one to iterate all values.

TODO: Add 'merge sorted arrays' and 'pivot' approach here TODO: Add 'prefix and suffix' and 'trapping rainwater' technique / Bag of Tokens

Subarray problems

A subarray is a subset of an array where all elements in the subarray needs to be contiguous. We can broadly categorize the techniques into three categories:

Hashmap

The idea is to use hashmap to store a property of the subarray like index, sum, product, etc. depending on the problem and then perform compuation based on that property to identify the required subarray.

General pattern of code:

// Question is to find number of subarrays which have sum equal to target
// https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/

int findSubarraySum(vector<int> &arr, int target) {
    // store sum as key and freq of sum as value
    unordered_map<int,int> mp;

    int ans = 0;
    int curr = 0;
    for (int i=0; i<arr.size(); ++i) {
        // add element to track curr sum so far
        curr += arr[i];

        // found the target; subarray from index [0,i]
        if (curr==target) ans++;

        // find (curr-target) in hashmap
        // If found that means subarray with sum target exists
        // where end element is 'i' and no of possible starts are
        // recorded in hashmap
        if (mp.find(curr-target) != mp.end()) {
            ans += mp[curr-target];
        }

        // update freq
        mp[curr]++;
    }
    return ans;
}

Practice problems:

Sliding Window

The idea is similar to two-pointers approach i.e. to track start and end of the subarray however it is so common in the subarray problems that it deserves its own category.

Usually you have to keep track of the start of the subarray. Other than that there are no general templates for it. More you practice, better it is. Try these different variety of problems:
Kadane's Algorithm

Maximum Product Subarray and Maximum Sum Subarray are two very important problems to understand for solving greedy/DP problems.

Binary search

Classic problems

Stock related problems is a popular category for interview questions. The idea simply is to maximize profit given some rules defined in the question. Just attempt the first two problems of the following series on the leetcode (attempt others if you know about DP approach):

Meeting room related problems is often asked in interview questions. The idea here is to sort the periods based on start time and then start clubbing periods by comparing end of previous group and start of current period.

← Previous
DSA Interview Notes: Binary Tree [Part 3]
Next →
DSA Interview Notes: Linked List [Part 2]