1-D Array

Practice Questions

size = sizeof(arr)/sizeof(arr[0]);

Q1: Reverse Array

void ReverseArray(vector<int>& arr, int m){
   int s = m + 1; // Condition for reversing whole array s = 0;    
   int e = arr.size() - 1;
   while(s <= e){
      swap(arr[s], arr[e]);
      s++;
      e--;
   }
}

Q2: Copying two sorted arrays into 3rd Array

void merge(vector<int>& arr1, int m, vector<int>& arr2, int n, vector<int>& arr3){
    int i = 0, j = 0, k = 0;

    while(i < m && j < n){   
        
        if(arr1[i] < arr2[j]){ 
            arr3[k++] = arr1[i++]; 
        }
        
        else { 
            arr3[k++] = arr2[j++];  
        }
    }
    
    // copy the remaining elements into the arr3
    while(i<m){ 
        arr3[k++] = arr1[i++]; 
    }

    while(j<n){
        arr3[k++] = arr3[j++];
    }
}

Q3: Merge Sorted Array

 nums1[m] = {1, 4, 5, 7, 0, 0, 0}  assume all zeros as an empty space. m -= n is the real size of an array, so the remaining elements are going to be merged with nums2 
 nums2[n] = {2, 3, 6}

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int j  = 0;
    while(j < n){ 
    
        nums1[m++] = nums2[j++]; 
    
    // nums1[m+n] = {1, 4, 5, 7, 2, 3, 6}
    }
    sort(nums1.begin(),nums1.end()); // sorting the unsorted array
}

Q4: Move Zeroes

void moveZeroes(vector<int>& arr) {
    int nonZero = 0; //This provides an index for all nonzero values
    for(int i = 0; i < arr.size(); i++){
        // ignore if 0 != 0 and increment the i++
        if(arr[i] != 0){
            swap(arr[i], arr[nonZero]);
            nonZero++;
        }
    } 
}

Q5: Rotate array to the right by k-Steps

Approach 1: Using STL Algorithm

Approach 2:

Rotate array to the right by k-Steps

    void rotate(vector<int>& v, int k) {
        int n = v.size();
        vector<int> temp (n);
    
        for(int i = 0; i < n; i++){
            temp[(i + k) % n] = v[i];
        }
        v = temp;
    }

Q6: Array left rotation by d positions

#include <iostream>
using namespace std;

int* rotateLeftByk(int* arr, int size, int k) {
    int *temp = new int[size];

    // approach # 1
    // for (int i = 0; i < size; i++) {
    //     temp[(i+size-k)%size] = arr[i];
    // }

    // approach # 2
    int j = 0; 
    for (int i = k; i < size; i++)
    {
        temp[j++] = arr[i];
    }

    for (int i = 0; i < k; i++)
    {
        temp[j++] = arr[i];
    }

    return temp;
}

int main() {
    int arr[] = {1, 2, 5, 9, 10};
    
    int* temp = rotateLeftByk(arr, 5, 2);

    for (int i = 0; i < 5; i++) {
        cout << temp[i] << " ";
    }
    
    delete[]temp;
}

Q7: Check if Array Is Sorted and Rotated

Recursive Approach

Case-I True

Sorted -> nuns[ ] = {1, 2, 3, 4, 5}

Case-II True

Sorted-Rotated -> nums[ ] = {3, 4, 5, 1, 2}

Case-III True

Same Element -> nums[ ] = {1, 1, 1, 1}

Case-IV False

Unsorted -> nums[ ] = {2, 1, 3, 4} Must use this I/P

// Sorted array = [1,2,3,4,5]
// Sorted-Rotated array = [3,4,5,1,2]

bool check(vector<int>& nums) {
    int count = 0;
    int n = nums.size();
    for(int i = 1; i < n; i++){
    // Condition for sorted-rotated array [3,4,5,1,2] -> (5 > 1) True
        if(nums[i-1] > nums[i])  count++;
    } 
    // Condition for Sorted Array [1,2,3,4,5]-> (5 > 1) True
    if(nums[0] < nums[n-1]) count++;

    return (count<=1); // count == 1 for same elements in an array like [1,1,1]
}

Q8: TwDo Sum

For Arrays

#include <iostream>
using namespace std;
int main() {
 
    int arr[] = {2, 3, 5, 7};
    int size = sizeof(arr)/sizeof(arr[0]);

    int target = 7;
    int temp[2];

    for (int i = 0; i < size; i++) {   
        bool found = false;
                    
        for (int j = i+1; j < size; j++) {
        
            if((arr[i] + arr[j]) == target) {
                temp[0] = i;
                temp[1] = j;
                found = true;
            }
        }
        if(found) break;
    }

    for (int i = 0; i < 2; i++) {
        cout << temp[i] <<" ";
    }
}

For Vector

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

Q9: Even elements appear first

#include <iostream>
using namespace std;

void rearrange(int* arr, int s) {
    int oddIndex = 0;
    for (int i = 0; i < s; i++) {
        if(arr[i]%2 == 0) {
            swap(arr[i], arr[oddIndex++]);
        }
    }
}

int main() {
    int arr[] ={1, 2, 3, 4, 5, 6};
    rearrange(arr, 6);

    for (int i = 0; i < 6; i++) {
        cout << arr[i] << " ";
    }
}

Q10: Remove Duplicates from Sorted Array

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        stack<int> st;
        st.push(nums[0]);
        
        for(int i = 1; i < nums.size(); i++) {
            if(st.top() != nums[i]) 
                st.push(nums[i]);   
        }
        nums.clear();
        while(!st.empty()) {
            nums.push_back(st.top());
            st.pop();
        }

        int s = 0, e = nums.size()-1;
        
        while(s<=e) swap(nums[s++], nums[e--]);
        
        return nums.size();
    }
};

Q11: Remove Duplicates from Sorted Array II

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        
        stack<int> st;
        
        for(int i = 0; i < nums.size(); i++) {

            if( st.empty() || (!st.empty() && st.top() != nums[i])  ) {
                st.push(nums[i++]);
                bool isRun = false;
                if(i < nums.size() && st.top() == nums[i]) {
                    st.push(nums[i]);
                    isRun = true;
                }
                if(isRun == false) i--;
            }  
        }
        
        nums.clear();

        while(!st.empty()) {
            nums.push_back(st.top());
            st.pop();
        }

        int s = 0, e = nums.size()-1;
        
        while(s<=e) swap(nums[s++], nums[e--]);
        
        return nums.size();
    }
};