1 August 2023

Solved my first hard question on Leetcode and one question on dynamic programming.

• Median of Two Sorted Arrays

My approach:

I solved it by merging two sorted arrays into one single sorted array.

My solution:

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();

        vector<int> arr(n+m,0);
        int i=0;
        int j=0;
        int k = 0;

        while(i<n && j<m){
            if(nums1[i]<nums2[j]){
                arr[k] = nums1[i];
                i++;
                k++;
            }else{
                arr[k] = nums2[j];
                j++;
                k++;
            }
        }


        while(i<n){
            arr[k] = nums1[i];
            i++;
            k++;
        }

        while(j<m){
            arr[k] = nums2[j];
            j++;
            k++;
        }

        if(k%2==0){
            double a = arr[(k/2)-1];
            double b = arr[(k/2)];
            double median = (a+b)/2;
            return median;
        }

        return arr[k/2];

    }
};

• Triangle

My approach:

This question is similar to min cost path to find in our general 2d array. In this, the only change was in the dimension of the array. So as long as we understand the pattern we can solve it. My very first solution was recursive with memoization but eventually, I figured out the do solution.

My solution:

• Recursion with Memoization

int helper(vector<vector<int>>& triangle, int n, int i, int j,int** arr){
    if(i>=n){
        return INT_MAX;
    }

    if(j>=triangle[i].size()){
        //j = 0;
        return INT_MAX;
    }

    if(i==n-1){
        return triangle[i][j];
    }

    if(arr[i][j]!=-1){
        return arr[i][j];
    }

    int a = helper(triangle,n,i+1,j,arr);
    int b = helper(triangle,n,i+1,j+1,arr);

    arr[i][j] = min(a,b)+triangle[i][j];

    return min(a,b)+triangle[i][j];
}

int minimumPathSum(vector<vector<int>>& triangle, int n){

    int pos = 0;

    int** arr = new int*[n];

    for(int i=0;i<n;i++){
        arr[i] = new int[i+1];
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<i+1;j++){
            arr[i][j] = -1;
        }
    }

    return helper(triangle,n,0,pos,arr);
}

• Dynamic Programming

int minimumPathSum(vector<vector<int>>& triangle, int n){
    // Write your code here.
    int pos = 0;

    int** arr = new int*[n];

    for(int i=0;i<n;i++){
        arr[i] = new int[i+1];
    }

    arr[0][0] = triangle[0][0];
    arr[0][1] = triangle[0][0];

    for(int i=1;i<n;i++){
        arr[i][0] = arr[i-1][0]+triangle[i][0];
    }

    for(int i=1;i<n;i++){

        for(int j=1;j<i+1;j++){

            if(j!=i){
                arr[i][j] = triangle[i][j]+min(arr[i-1][j-1],arr[i-1][j]);
            }else{
                arr[i][j] = triangle[i][j]+arr[i-1][j-1];
            }

        }
    }

    int minTotal = INT_MAX;
    for(int j=0;j<n;j++){
        minTotal = min(minTotal,arr[n-1][j]);
    }

    return minTotal;

}