Solving Array Coding Problems

Solving Array coding problems with explanation

Photo by Nick Hillier on Unsplash

1. Question list

1. Subarray with given sum G4G, Leetcode Easy Google
2. Missing number in array G4G Leetcode Easy
3. Sorting an array containing 0’s, 1’s and 2’s G4G Techie Easy
4. Product of array except self G4G Leetcode Medium
5. Find triplets with zero sum G4G Leetcode Mediumtodo
6. Rotate array G4G Leetcode Medium todo
7. Find All Duplicates in an Array G4G Leetcode Medium todo
8. K’th smallest/largest element G4G Leetcode Techie Medium todo
9. In place merge two sorted arrays G4G Leetcode Techie Medium todo
10. Maximum sum increasing subsequence G4G Medium DP todo

2. C++ Implementation

Subarray with given sum

Given an unsorted array A of size N of non-negative integers, find a continuous sub-array that adds to a given number.

void subArraySum(int a[], int n, int val){
    int start = 0, end = 0, sum = 0;
    for(int i = 0; i < n; i++){
        end = i;
        sum += a[i];
        while(sum > val && start < n){
            sum -= a[start];
            start++;
        }
        if(sum == val){
            cout << start + 1 << " " << end + 1 << endl;
            return;
        }
    }
    cout << -1 << endl;
}

• Explanation

1. The number of subarrays is uncertain, so we use start and end to track the indices.
2. When the current sum > target, we keep subtracting the number from num from the beginning.
3. Time complexity looks more than O(n), but if we take a closer look at the program, then we can figure out the time complexity is O(n). We can prove it by counting the number of operations performed on every element of a[] in the worst case. There are at most 2 operations performed on every element: (a) the element is added to the sum (b) the element is subtracted from the sum. So the upper bound on the number of operations is 2n which is O(n).
4. The above solution doesn’t handle negative numbers. We can use hashing to handle negative numbers.

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map <int, int> map;
    vector <int> result;
    for(int i = 0; i < nums.size(); i++){
        if (map.end() != map.find(target-nums[i])){
            result.push_back(map[target-nums[i]]);
            result.push_back(i);
        }else{
            map[nums[i]] = i;
        }
    }
    return result;
}

• Explanation

1. We need to output the indices of two numbers (may not be continuous), use the hash to store the index and the value (note that the key of the map is the value of the element, the value of the map is the index of that element).
2. For each element, we first check if there is an element in the hash table that adds the current element up to the target value, if not, we store the info in the table.
3. As finding an element in the hash table takes constant time, this implementation gives us time complexity of O(n) as we only need to go through each element once.

Missing number in array

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

int missingNumber(vector<int>& nums) {
    int sum = 0;
    int n = nums.size();
    sum = n*(n+1)/2;
    for (auto i: nums){
        sum -= i;
    }
    return sum;
}

• Explanation

1. The array contains continuously increasing numbers, we can calculate the sum of these numbers (suppose no missing number) first, then subtracts each element in the array to get the missing number.
2. Use n*(n+1)/2 to improve efficiency

Sorting an array containing 0’s, 1’s and 2’s

Given an array A[] consisting of 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

1. Easy solution (count sort)

We count the number of 0’s, 1’s, and 2’s and then put them in the array in their correct order, time complexity is O(n) but it requires two traversals of the array.

2. Similar to 3-way partitioning for Dutch national flag problem

void sort012(int a[], int n){
    int lo = 0, mid = 0;
    hi = n - 1;
    while(mid <= hi){ // track mid as current element
        if(a[mid] == 0)
            swap(&a[lo++], &a[mid++]);//ele<=mid are sorted, so mid++
        else if (a[mid] == 1)
            mid++;
        else if (a[mid] == 2)
            swap(&a[mid], &a[hi--]);
    }
}

• Explanation

1. Separate the value into 3 groups, i.e: less than 1, equal to 1, and greater than 1.
2. Track iterate elements with index mid , lo for those less than 1 and hi for those greater than 1.
3. When the value is less than 1, means we found an element for lo , we swap the value and increase both lo and mid . If the value is 1, we simply increase the index, if the value is 2, we need to swap the current value with the hi one.
4. The elements with an index less than mid can be either 0 or 1, while the elements with an index greater than mid can be 0, 1, or 2. Thus the loop condition is mid≤hi as there is a chance the element of index mid and hi can be 0, which needs to be swapped, see example below (step 5).

array: 0 1 2 2 0 1
init: lo = 0, mid = 0, hi = 5
step 1: 0 1 2 2 0 1, lo = 1, mid = 1, hi = 5
step 2: 0 1 2 2 0 1, lo = 1, mid = 2, hi = 5
step 3: 0 1 1 2 0 2, lo = 1, mid = 2, hi = 4
step 4: 0 1 1 2 0 2, lo = 1, mid = 3, hi = 4
step 5: 0 1 1 0 2 2, lo = 1, mid = 3, hi = 3
step 6: 0 0 1 1 2 2, lo = 2, mid = 4, hi = 3

Product of array except self

Given an array nums of n integers where n > 1, return an array outputsuch that output[i] is equal to the product of all the elements of nums except nums[i].

Input:  [1,2,3,4]
Output: [24,12,8,6]
2x3x4, 1x3x4, 1x2x4, 1x2x3
vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> res;
    int product = 1;
    for(int i = 0; i < nums.size(); i++){
        res.push_back(product);
        product *= nums[i];
    }
    product = 1;
    for(int i = nums.size()-1; i >= 0; i--){
        res[i] *= product;
        product *= nums[i];
    }
    return res;
}

• Explanation

1. First store the values contains the product of all elements on left of nums[i] excluding nums[i].
2. Then calculate the values contains the product of all elements on the right of nums[i] excluding nums[i].
3. For instance, in the first loop, when i is 0, we only store 1 in the result as we should calculate the product of the elements on the right of nums[0]. i.e. res[0] = nums[1]*nums[2]…*nums[n-1].
4. It may require to check the case where the number of elements is 0 or 1.

• Where I got stuck

1. I could only implement it with a brute force solution in the beginning.
2. The key to improving it is to observe how the products are calculated for each element and try to solve it with O(n) time.

For more array questions, see Leetcode, G4G, and Techie Delight.