Day 6 (30 Days of Code)

5 July 2023

Today was yet another day of DSA only. I solved 4 Leetcode questions today.

What did I learn?

The approach I used to make the solution optimized is called sliding window. It was later found that my approach has a specific name.

• Pascal's Triangle

My approach:

This question will take O(n^2) time no matter what you do. However, it was still good learning to solve this question.

My solution:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        if(numRows==1){
            return {{1}};
        }

        vector<vector<int>> output;
        output.push_back({1});
        for(int i=1;i<numRows;i++){
            vector<int> count;
            count.push_back(1);

            for(int j=1;j<i;j++){
                int sum = (output.at(i-1)).at(j-1) + (output.at(i-1)).at(j);
                count.push_back(sum);
            }
            count.push_back(1);
            output.push_back(count);
        }
        return output;
    }
};

• Pascal's Triangle II

My approach:

Since it was specified that the space complexity of the algorithm should be linear so I came up with a solution that has linear space complexity.

My solution:

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        if(rowIndex==0){
            return {1};
        }

        vector<int> output;
        output.push_back(1);

        for(int i=1;i<=rowIndex;i++){
            output.push_back(1);
            int prev = output[0];

            for(int j=1;j<i;j++){
                int sum = prev+output[j];
                prev = output[j];
                output[j] = sum;
            }

        }
        return output;
    }
};

• Best Time to Buy and Sell Stock

My approach:

At first, I solved this using brute force which gave me the time complexity of O(n^2). However Leetcode rejected my solution for bigger test cases. I then came up with the solution with O(n) time complexity. This is where I used sliding window technique.

My solution:

1. Brute Force solution [O(n^2)]

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

2. Optimized solution [O(n)]

    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int maxProfit = 0;
   
            int start = prices[0];
            int highest = 0;
   
            for(int i=1 ; i<prices.size() ; i++){
                if(start>prices[i]){
                    start = prices[i];
                }
                else if(start<prices[i]){
                    highest = max(prices[i]-start,highest);
                }
            }
            return highest;
   
        }
    };
   

• Longest Subarray of 1's After Deleting One Element

My approach:

I was able to come up with the solution in linear time complexity using a sliding window. However, it was later I realized that it is not necessary and reduced the extra line of code I wrote.

1. Using sliding window [O(n)]

    class Solution {
    public:
        int longestSubarray(vector<int>& nums) {
            int maxSub = 0;
            int firstCount = 0;
            int secondCount = 0;
            bool del = false;
   
            for(int i=0 ; i<nums.size() ; i++){
                if(nums[i]!=1 && del==false){
                    del = true;
                }
                else if(nums[i]!=1 && del==true){
                    del = false;
                    maxSub = max(firstCount+secondCount,maxSub);
                    i = i-secondCount-1;
                    firstCount = 0;
                    secondCount = 0;
                }
                else if(nums[i]==1 && del==true){
                    secondCount++;
                }
                else if(nums[i]==1 && del==false){
                    firstCount++;
                }
   
            }
   
            if((firstCount!=0 && secondCount==0) && del==false){
                return firstCount-1;
            }
            if(del==true){
                maxSub = max(firstCount+secondCount, maxSub);
            }
   
            return maxSub;
   
        }
    };
   

2. Without using sliding window [O(n)]

    class Solution {
    public:
        int longestSubarray(vector<int>& nums) {
            int maxSub = 0;
            int firstCount = 0;
            int secondCount = 0;
   
            for(int i=0;i<nums.size();i++){
                if(nums[i]==1){
                    firstCount;
                }
                else{
                    maxSub = max(maxSub, firstCount+secondCount);
                    firstCount=secondCount;
                    secondCount=0;
                }
            }
            maxSub=max(maxSub,firstCount+secondCount);
            if(maxSub==nums.size()){
                return maxSub-1;
            }
            return maxSub;
        }
    };