Skip to main content
HashnodeCPP_DSA

Command Palette

Search for a command to run...

Array Problems

Updated
•10 min read
R
Rajesh Gurajala

In this article we will be solving problems on arrays

EASY QUESTIONS

Smallest Missing Multiple of K

class Solution {
public:
    int missingMultiple(vector<int>& nums, int k) {
        unordered_set<int> s(nums.begin(), nums.end());
        while(true) for(int i=k; ; i+=k) if(s.find(i)==s.end()) return i;
    }
};

No further time complexity and space complexity optimisations possible.

Rearrange Array Elements by Sign

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        vector<int> positives, negatives;
        for(int x:nums){
            if(x>0) positives.push_back(x);
            else negatives.push_back(x);
        }
        for(int i=0; i<nums.size(); i++){
            if(i%2==0) nums[i]=positives[i/2];
            else nums[i]=negatives[i/2];
        }
        return nums;
    }
};

It is impossible to optimize space complexity further.

Missing and Repeating Number

class Solution {
public:
    vector<int> findTwoElement(vector<int>& arr) {
        int n = arr.size();
        long long actual_total = 1LL * n * (n + 1) / 2, calculated_total = 0;
        for(int i : arr) calculated_total += i;

        int repeated, missing;
        for(int i = 0; i < n; i++){
            int idx = abs(arr[i]) - 1;
            if(arr[idx] < 0) repeated = abs(arr[i]);
            else arr[idx] *= -1;
        }
        missing = (int)(actual_total - (calculated_total - repeated));
        return { repeated, missing };
    }
};

Leaders in an Array

class Solution {
  public:
    vector<int> leaders(vector<int>& arr) {
        vector<int> result;
        int n=arr.size();
        result.push_back(arr[n-1]);
        int maxIndex=n-1;
        for(int i=n-2; i>=0; i--){
            if(arr[i]>=arr[maxIndex]){ result.push_back(arr[i]); maxIndex=i; }
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

Rotate Array

Optimal ( o(N) time complexity )

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if(n == 0) return;
        k %= n;

        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

Merge Intervals

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        sort(intervals.begin(), intervals.end());
        result.push_back(intervals[0]);
        for(int i=1; i<intervals.size(); i++){
            vector<int>& last=result.back();
            if(last[1]>=intervals[i][0])last[1]=max(last[1], intervals[i][1]);
            else result.push_back(intervals[i]);
        }
        return result;
    }
};

Note:

&last is used instead of a temp popping out, verifying and again pushing back, to make changes by reference.

Remove Duplicates from an array

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow=0, fast=0, n=nums.size();
        while(fast<n){
            if(nums[slow]!=nums[fast]){
                slow++;
                nums[slow]=nums[fast];
            }
            fast++;
        }

        return slow+1;
    }
};

Move Zeroes

class Solution {
public:

    void moveZeroes(vector<int>& nums) {
        int n=nums.size();
        int slow=0, count=0;
        for(int i=0; i<n; i++){
            if(nums[i]!=0){nums[slow]=nums[i]; slow++;}
            else count++;
        }
        for(int i=0; i<count; i++) nums[n-1-i]=0;
    }
};

Merge Sorted Array

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=m-1, j=n-1, k=m+n-1;
        while(i>=0 && j>=0){
            if(nums1[i]>=nums2[j]) nums1[k--]=nums1[i--];
            else if(nums1[i]<nums2[j]) nums1[k--]=nums2[j--];
        }
        while(j>=0) nums1[k--]=nums2[j--];
    }
};

Sort Colors

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        int zeroindex=0, twoindex=n-1;
        int i=0;
        while(i<=twoindex){
            if(nums[i]==0){ swap(nums[i], nums[zeroindex++]); i++;}
            else if(nums[i]==2) swap(nums[i], nums[twoindex--]);
            else i++;
        }
    }
};

Here,

We increamented at 0 but not at 2 because after swapping at 2 we might get 0 at i. So to again recheck we didnt do i++ at nums[i]==2.

MEDIUM QUESTIONS

Majority Element

1) Brute Force ( o(N) time complexity, o(N) space complexity )

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> m;
        for(int i=0; i<nums.size(); i++) m[nums[i]]++;
        int maxTimes=0, maxElement=0;
        for(auto &[key, value] : m) if(value>maxTimes){maxTimes=value; maxElement=key;}
        return maxElement;
    }
};

2) Optimal ( o(N) time complexity, o(1) space complexity ) [ Boyer Moore Voting Algorithm ]

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate=nums[0], count=1;
        for(int i=1; i<nums.size(); i++){
            if(count==0){ candidate=nums[i]; count=1; }
            else{
                if(nums[i]==candidate) count++;
                else count--;
            }
        }
        return candidate;
    }
};

Majority Element II

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
       int n=nums.size();
       int ele1=INT_MIN, ele2=INT_MIN, count1=0, count2=0;

       for(int i=0; i<n; i++){
        if(count1==0 && nums[i]!=ele2){ele1=nums[i]; count1=1;}
        else if(count2==0 && nums[i]!=ele1){ele2=nums[i]; count2=1;}
        else if(nums[i]==ele1) count1++;
        else if(nums[i]==ele2) count2++;
        else { count1--; count2--; }
       }

       count1=0; count2=0;
       for(int i=0; i<n; i++){
        if(nums[i]==ele1) count1++;
        if(nums[i]==ele2) count2++;
       }

       vector<int> result;
       if(count1>n/3) result.push_back(ele1);
       if(count2>n/3) result.push_back(ele2);
       return result;
    }
};

2 Sum

1) Brute Force ( o(N²) time complexity ) // Checking all possibilities

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
       for(int i=0; i<nums.size()-1; i++) for(int j=i+1; j<nums.size(); j++) if(nums[i]+nums[j]==target) return {i,j};
       return {};
    }
};

2) Optimal ( o(N) time complexity , o(N) space complexity ) // Using Hash Map

class Solution {
public:

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

3Sum

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n=nums.size();
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;

        for(int i=0; i<n && nums[i]<=0; i++){
            if(i>0 && nums[i]==nums[i-1]) continue;
            int target=-1*nums[i], j=i+1, k=n-1;
            while(j<k){
                int total = nums[j]+nums[k];
                if(total==target){
                    result.push_back({nums[i], nums[j], nums[k]});
                    int prev1=nums[j], prev2=nums[k];
                    while(j<n && nums[j]==prev1) j++;
                    while(k>0 && nums[k]==prev2) k--;
                }
                else if(total<target) j++;
                else k--;
            }
        }
        return result;
    }
};

Note:

The 3 sum problem is solved in this way.

Suppose 3 numbers x, y and z sum up to zero. We sort the nums array first. And then we traverse through the array, and fix i-Th element as x. Now we need y and z which sum up to the target -x.

Now the problem became a 2 sum problem. But as the array is already sorted, we don’t need a hash map. Instead, 2 pointers are enough to solve this problem.

Fix pointer j at i+1 Th position and pointer k at n-1 position.

Now if sum of nums[j] and nums[k] is equal to target, we got a solution at i, j, k elements. Else if sum is less than target we do j++, as we need bigger element. Else if sum is greater than target we do k—, as we need smaller elements.

In 2-sum problem, if input array is sorted, we can solve this way instead of using a hash map.

4Sum

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
     int n = nums.size();
     vector<vector<int>> result;
     sort(nums.begin(), nums.end());

     for(int i=0; i<n; i++){
         if(i>0 && nums[i]==nums[i-1]) continue;

        for(int j=i+1; j<n; j++){
             if(j>i+1 && nums[j]==nums[j-1]) continue;

            long long tgt = 1LL * target - nums[i] - nums[j], l=j+1, r=n-1;
            while(l<r){
                long long total = 1LL * nums[l] + nums[r];
                if(total==tgt){
                    result.push_back({nums[i], nums[j], nums[l], nums[r]});

                    int prev1 = nums[l], prev2 = nums[r];
                    while(l<n && nums[l]==prev1) l++;
                    while(r>=0 && nums[r]==prev2) r--;
                }
                else if(total<tgt) l++;
                else r--;
            }
        }
     }

     return result;
    }
};

Note:

The ideology is same as 3 sum problem, where we consider i iterates from start to end of nums array and j starts from i+1 and k from n-1.

Here, i iterates from start to end, j starts from i+1, and l from j+1 and r from n-1.

Interesting Fact:

Both are equivalent to each other This is used so that we don’t need to type every operator on right hand side.

long long tgt = 1LL * target - nums[i] - nums[j];

long long tgt = (long long)target - (long long)nums[i] - (long long)nums[j];

Longest Balanced Subarray I

class Solution {
public:
    int longestBalanced(vector<int>& nums) {
        int n = nums.size(), maxLength=0;
        for(int i=0; i<n; i++){
            int balance=0;
            unordered_map<int,int> m;
            for(int j=i; j<n; j++){
                if(m.find(nums[j])==m.end()){
                    if(nums[j]%2==0) balance++;
                    else balance--;
                    m[nums[j]]=j;
                }
                if(balance==0) maxLength=max(maxLength, j-i+1);
            }
        }
        return maxLength;
    }
};

The only possible optimisation is using a lazy segment tree which can be discussed later.

Longest sub array with given sum K(for both positives, positives+negatives)

When it comes to sub sequence, where elements can be continuous or non continuous, we solve with recursion, where we can consider a temp array, and either pick / not pick a element.

But sub arrays should be continuous.

1) Brute Force ( o(N³) time complexity )

class Solution {
public:

    int longestSubarray(vector<int> &nums, int k) {
        int n=nums.size();
        int max=0;
        for(int i=0; i<n; i++){
            for(int j=i; j<n; j++){
                int sum=0;
                for(int k=i; k<=j; k++) sum+=nums[k];
                int count=j-i+1;
                if(sum==k && count>max) max=count;
            }
        }
        return max;
    }
};

2) Better ( o(N²) time complexity , o(N) space complexity) [ storing sum in vector]

class Solution {
public:

    int longestSubarray(vector<int> &nums, int k) {
        int n=nums.size();

        vector<int>total(n,0);
        total[0]=nums[0];
        for(int i=1; i<n; i++) total[i]=total[i-1]+nums[i];

        int max=0;
        for(int i=0; i<n; i++){
            for(int j=i; j<n; j++){
                int sum=total[j]-total[i]+nums[i];
                int count=j-i+1;
                if(sum==k && count>max) max=count;
            }
        }
        return max;
    }
};

3) Optimal ( o(N) time complexity , o(N) space complexity) [ storing sum, index in hash map ]

class Solution {
public:
    int longestSubarray(vector<int> &nums, int k) {
        unordered_map<int,int> m;
        int prefix = 0, maxLen = 0;

        for (int i = 0; i < nums.size(); i++) {
            prefix += nums[i];

            if (prefix == k) maxLen = i + 1; 
            else if (m.find(prefix - k) != m.end()) maxLen = max(maxLen, i - m[prefix - k]);

            // store first occurrence only
            if (m.find(prefix) == m.end()) m[prefix] = i;
        }
        return maxLen;
    }
};

Note:

  1. prefix==k, means sub array from index 0 to i, which is largest sub array we found so far.

  2. we only store first occurrence as 2nd occurrence will always have less length than 1st one.

Sub array sum equals k

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
      int n=nums.size();
      int prefix=0, count=0;
      unordered_map<int,int> m;

      for(int i=0; i<n; i++){
        prefix+=nums[i];
        if(prefix==k) count++;
        if(m.find(prefix-k) != m.end()) count+=m[prefix-k];  
        m[prefix]++;
      }  
      return count;
    }
};

Note:

Here else if is not used for second condition unlike previous problem. Because if prefix==k, then prefix-k=0; then if x sub arrays obey that condition, then we also get x more sub arrays by removing them because k minus zero is still k.

Whereas in previous question as we needed longest, we don’t want to remove those zero sub arrays, so we used else if.

Count Subarrays with given XOR

class Solution {
  public:
    long subarrayXor(vector<int> &arr, int k) {
        int prefix=0;
        long count=0;
        unordered_map<int,int> m;
        for(int i=0; i<arr.size(); i++){
            prefix^=arr[i];
            if(prefix==k) count++;
            if(m.find(prefix^k) != m.end()) count+=m[prefix^k];
            m[prefix]++;
        }
        return count;
    }
};

Next Permutation

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i=n-2;
        while(i>=0 && nums[i]>=nums[i+1]) i--;

        if(i>=0){
        int j=n-1;
        while(nums[j]<=nums[i]) j--;
        swap(nums[i], nums[j]);
        }

        reverse(nums.begin()+i+1, nums.end());
    }
};

Note:

To find the next permutation, we have to look from last.

From last we have to track until where the ascending order breaks; if it breaks at i, stop there.

Now from the end find j which is greater than i, swap them.

Now reverse from nums.begin()+i+1 to the nums.end()

2-D MATRIX QUESTIONS

Rotate Image By 90 deg

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();

        for(int i=0; i<n; i++){    // swap
            for(int j=i+1; j<n; j++) swap(matrix[i][j], matrix[j][i]);
        } 

        for(int i=0; i<n; i++){    // reverse
            for(int j=0; j<n/2; j++) swap(matrix[i][j], matrix[i][n-1-j]);
        } 
    }
};

Additional Tip:

90 = transpose + reverse row
180 = reverse row + reverse column
270 = transpose + reverse col

Set Matrix Zeroes

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();

        // identify zeroes at 1st row and 1st col
        bool firstRowZeroes=false, firstColZeroes=false;
        for(int i=0; i<n; i++) if(matrix[0][i]==0) firstRowZeroes=true;
        for(int i=0; i<m; i++) if(matrix[i][0]==0) firstColZeroes=true;

        // identify zeroes at rows and cols except 1st row and 1st col
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }

        // make rows zero
        for(int i=1; i<m; i++)if(matrix[i][0]==0){
            for(int j=1; j<n; j++) matrix[i][j]=0;
        }

        // make cols zero
        for(int i=1; i<n; i++) if(matrix[0][i]==0){
            for(int j=1; j<m; j++) matrix[j][i]=0;
        }

        // make 1st row zero
         if(firstRowZeroes) for(int i=0; i<n; i++) matrix[0][i]=0;

         // make 1st col zero
         if(firstColZeroes) for(int i=0; i<m; i++) matrix[i][0]=0;
    }
};

Spiral Matrix

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> result;
        int m=matrix.size(), n=matrix[0].size();

        int left=0, right=n-1, top=0, bottom=m-1;
        while(left<=right && top<=bottom){
            for(int i=left; i<=right; i++) result.push_back(matrix[top][i]);
            top++;
            for(int i=top; i<=bottom; i++) result.push_back(matrix[i][right]);
            right--;
            if(top<=bottom){
                for(int i=right; i>=left; i--) result.push_back(matrix[bottom][i]);
                bottom--;
            }
            if(left<=right){
                for(int i=bottom; i>=top; i--) result.push_back(matrix[i][left]);
                left++;
            }
        }
        return result;
    }
};
#cpp#array#arrays#dsa#data-structures#algorithms

Comments

Join the discussion

No comments yet. Be the first to comment.

More from this blog

CPP_DSA

6 posts