Assignments - DSA

TLE ka koi ilaz noi

Q1: Two Sum II - Input Array Is Sorted

For sorted Arrays - O(lgn)

class Solution {
public:
    
    vector<int> twoSum(vector<int>& numbers, int target) {
        int sum;
        int s= 0; int e = numbers.size()-1;
        while(s <= e) {
            sum = numbers[s] + numbers[e];
            if(sum == target) return {s+1, e+1};
            if(sum > target) e--;
            else s++;
        }
        return {};
    }
};

For unSorted Arrays - O(n)

class Solution {
public:
    
    void searchSecElem(vector<int>& nums, int fElem, int& j, int s, int e, int target) {
        if(s>=e) {
            if(fElem + nums[s] == target) j = s;
            return;
        }
        int mid = s+(e-s)/2;
        searchSecElem(nums, fElem, j, s, mid, target);
        searchSecElem(nums, fElem, j, mid+1, e, target);
    }

    vector<int> twoSum(vector<int>& numbers, int target) {
        int j = -1;
        vector<int> res(2, -1);
        for(int i = 1; i < numbers.size(); i++) {
            searchSecElem(numbers, numbers[i-1], j, i, numbers.size()-1, target);
            if(j!=-1) {
                res[0] = i-1+1;
                res[1] = j+1;
                return res;
            }
        }
        return res;
    }
};

Q2: Find Minimum in Rotated Sorted Array II & Find Minimum in Rotated Sorted Array --- upvote - Solution 👍

class Solution {
public:
    
    void searchMinimum(vector<int>& nums, int& min, int s, int e) {
        if(s >= e) {
            if(min > nums[s]) min = nums[s];
            return;
        }
        
        int mid = s+(e-s)/2;
        searchMinimum(nums, min, s, mid);
        searchMinimum(nums, min, mid+1, e);
    }

    int findMin(vector<int>& nums) {

        int min = INT_MAX;
        searchMinimum(nums, min, 0, nums.size()-1);
        return min;
        
    }
};

Q3. 53. Maximum Subarray

Divide & Conquer (Modified - quite easy) - O(nlgn)

class Solution {
public:
    
    void findMaxiSum(vector<int>& nums, int s, int e, int& newSum, int& curSum) {
        if(s>=e) {
            newSum += nums[s];
            if(newSum > curSum) curSum = newSum;
            return;
        }
        int mid = s+(e-s)/2;
        findMaxiSum(nums, s, mid, newSum, curSum);
        findMaxiSum(nums, mid+1, e, newSum, curSum);
    }

    int maxSubArray(vector<int>& nums) {
        int oldSum = INT_MIN;
        for(int i = 0; i < nums.size(); i++) {
            int newSum = 0, curSum = INT_MIN;
            findMaxiSum(nums, i, nums.size()-1, newSum, curSum);
            if(curSum > oldSum) oldSum = curSum;
        }
        return oldSum;
    }
};

Divide & Conquer - O(nlgn)

class Solution {
public:

    int findMaxCrossSubArr(vector<int>& arr, int s, int e, int mid) {
        int leftSum = INT_MIN;
        int sum = 0;
        
        for(int i = mid; i >= 0; i--) {
            sum += arr[i];
            if(sum > leftSum) leftSum = sum;
        }

        int rightSum = INT_MIN;
        sum = 0;

        for(int i = mid+1; i <= e; i++) {
            sum += arr[i];
            if(sum > rightSum) rightSum = sum;
        }
        return (leftSum + rightSum);
    }

    int findMaxiSubArr(vector<int>& arr, int s, int e) {
        if(s>=e) return arr[s];

        int mid = s+(e-s)/2;
        int LSS = findMaxiSubArr(arr, s, mid);
        int RSS = findMaxiSubArr(arr, mid+1, e);
        
        int CSS = findMaxCrossSubArr(arr, s, e, mid);
        
        return max(max(LSS, RSS), CSS);
    }

    int maxSubArray(vector<int>& arr) {
        return findMaxiSubArr(arr, 0, arr.size()-1);
    }
};

Kadane's Algorithm - O(n)

class Solution {
public:

    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int maxSum = INT_MIN;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            maxSum = max(maxSum, sum);
            if(sum < 0) sum = 0;
        }
        return maxSum;
    }
};

Q4: Reverse Pairs

class Solution {
public:

    void findPair(vector<int>& nums, int firstElem, int s, int e, int& count) {
        if(s >= e) {
            if(firstElem > 2*(long long) nums[s]) count++;
            return;
        }
        int mid = s+(e-s)/2;
        findPair(nums, firstElem, s, mid, count);
        findPair(nums, firstElem, mid+1, e, count);
    }

    int reversePairs(vector<int>& nums) {
        int count = 0;
        for(int i = 0; i < nums.size()-1; i++) {
            findPair(nums, nums[i], i+1, nums.size()-1, count);
        }
        return count;
    }
};

Q5: Count of Smaller Numbers After Self

class Solution {
public:
    
    void counter(vector<int>& nums, int firstElem, int s, int e, int& count) {
        if(s >= e) {
            if(firstElem > nums[s]) count++;
            return;
        }
        int mid = s+(e-s)/2;
        counter(nums, firstElem, s, mid, count);
        counter(nums, firstElem, mid+1, e, count);
    }
    
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size(), 0);
        int count;
        for(int i = 0; i < nums.size()-1; i++) {
            count = 0;
            counter(nums, nums[i], i+1, nums.size()-1, count);
            res[i] = count;
        }
        //No element is present on the right side after last element.  
        res[nums.size()-1] = 0;
        return res;
    }
};

Q6: Median of Two Sorted Arrays

class Solution {
    int i = 0, j = 0;
    double med;
public:
    void sol(vector<int>& nums1, vector<int>& nums2, int t_size, int elem, int& call) {
        if(i == nums1.size() && j == nums2.size()) { 
            return;
        }

        if(i < nums1.size() && j < nums2.size()) {
            if(nums1[i] <= nums2[j]) {
                elem = nums1[i++];
                sol(nums1, nums2, t_size, elem, ++call);
            }
            else if(nums1[i] >= nums2[j]) {
                elem = nums2[j++];
                sol(nums1, nums2, t_size, elem, ++call);
            }
        }
        else {
            if(i < nums1.size()) {
                elem = nums1[i++];
                sol(nums1, nums2, t_size, elem, ++call);
            }
            else if(j < nums2.size()) {
                elem = nums2[j++];
                sol(nums1, nums2, t_size, elem, ++call);
            }
        }
        call--;
        cout << call<<"-"<<elem<<", "; 
        
        
        // case for even size arrays
        if(t_size % 2 == 0) {
            if(t_size/2 == call || (t_size/2)-1 == call) {
                med += elem/2;
                if(elem%2==1) med += 0.5;
            }
        }
        
        // case for odd size arrays
        else if(t_size % 2 == 1) {
            if(t_size/2 == call){
                cout << t_size/2;
                med = elem;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int t_size = nums1.size() + nums2.size();
        int call = 0;
        int elem;
        sol(nums1, nums2, t_size, elem, call);
        return med;
    }
};