35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

Approach 1: Use modified binary search to get the required index

class Solution {
public:
    // recursive modified binary search
    int insertPos(vector<int> &nums, int low, int high, int target){
        //base case with 1 element
        if(low == high){
            if(nums[low] < target){
                return low + 1;
            }else{
                return low;
            }
        }
        //base case with 2 elements
        if(low == high - 1){
            if(nums[high] < target){
                return high + 1;
            }else if(target <= nums[low]){
                return low;
            }else{
                return high;
            }
        }
        //recursive call based on the index 
        int mid = low + ((high - low) >> 1);
        if(nums[mid] == target){
            return mid;
        }else if(nums[mid] < target && nums[mid + 1] > target){
            return mid + 1;
        }else if(nums[mid] > target){
            return insertPos(nums, low, mid - 1, target);
        }else{
            return insertPos(nums, mid + 1, high, target);
        }
    }
    
    int searchInsert(vector<int>& nums, int target) {
        return insertPos(nums, 0, nums.size()-1, target);
    }
};

Approach 2: Use lower_index() method supported by STL

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        vector<int>::iterator it = lower_bound(nums.begin(), nums.end(), target);
        return (it - nums.begin());
    }
};

Here is the link to the ideone solution : http://ideone.com/TbFRxX

Read More

26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,:

Given input array nums = [1,1,2], your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

Approach:

1. Copy the current element to the current index if it does not match to the previous element, else move to the next element and repeat the same for all elements of the array.

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

Here is the link to the ideone solution : http://ideone.com/T4iddh

Read More

Majority Element in a Sorted Array

Write an algorithm to find if a given integer x appears more than n/2 times in a sorted array of n integers. See this for a similar problem on Majority Element.

Approach: Use binary search to find the first occurrence of x in the array.
TC  = O(log(n)) 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include <iostream> #include <cmath> using namespace std; int binsrch(int *arr, int x, int low, int high){ if(low <= high){ int mid = (low + high) / 2; // returns the first occurrence of x if(arr[mid] == x && (arr[mid] > arr[mid - 1] || mid == 0)){ return mid; } if(x > arr[mid]){ return binsrch(arr, x, mid + 1, high); } else{ return binsrch(arr, x, low, mid - 1); } } return -1; } int isMajority(int *arr, int x, int n){ int first = binsrch(arr, x, 0, n - 1); if(first == -1){ return 0; } if((first + n/2) <= (n - 1) && arr[first + n/2] == x){ return 1; } return 0; } using namespace std; int main(){ int arr[] ={1, 2, 3, 4, 4, 4, 4}; int n = sizeof(arr)/sizeof(arr[0]); int x = 4; if(isMajority(arr, x, n)){ cout << x << " is the majority element." << endl; } else{ cout << x << " is not the majority element." << endl; } return 0; }

Read More

Remove Duplicates from Sorted Array II

Modification of the problem "Remove Duplicates":
What if the duplicates are allowed at most twice in the resulting array?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

int Solution::removeDuplicates(vector<int> &nums) { if(nums.size() == 0){ return 0; } int count = 1; int j = 1; for(int i = 1 ; i < nums.size(); i++){ if(nums[i] != nums[i - 1]){ nums[j] = nums[i]; count = 1; j++; } else if(count == 1){ nums[j] = nums[i]; count = 2; j++; } } return j; }

Read More