Day 2 (30 Days of Code)

1 July 2023

Today I revised Recursion and redid the questions that I did previously. Apart from those I did 3 easy questions on LinkedIn. However, the 2 questions I did can easily be done without recursion but I did them through recursion just for more practice and fun.

What did I learn?

I realized that we should not use recursion in the DSA problems until it's either told or there is no other way. However, just trying to solve a problem through recursion enhances your understanding.

1. Remove Duplicates from Sorted Array

My approach:

Since I wanted to try recursion so I solved it through recursion. However, it was not the best way to do it so came up with a better solution.

My solution:

• Recursive:

    class Solution {
    public:
  
        int helper(vector<int>& nums,int s,int e){
            if(nums.size()==0){
                return 0;
            }
            if(s>=e){
                return 1;
            }
  
            int ans = helper(nums,s+1,e);
  
            if(nums[s]==nums[s+1]){
                for(int i=s+1;i<nums.size();i++){
                    nums[i-1] = nums[i];
                }
                nums.pop_back();
                return ans;
            }
            return ans+1;
  
        }
  
        int removeDuplicates(vector<int>& nums) {
            int output = helper(nums,0,nums.size()-1);
            return output;  
        }      
    };
  

• Optimized solution:

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

  Writing an optimized solution for this is something I learned new today.

1. Remove Element

My approach:

Just like the previous question I tried solving it through recursion which worked however it was yet again not the best way to solve it.

My solution:

• Recursive:

    class Solution {
    public:
  
        int helper(vector<int>& nums,int val,int s,int e){
            if(s>=e){
                if(s==e && nums[s]==val){
                    nums.pop_back();
                    return 0;
                }
                return 1;  
            }
  
            int ans = helper(nums,val,s+1,e);
  
            if(nums[s]==val){
                for(int i=s+1;i<nums.size();i++){
                    nums[i-1] = nums[i];
                }
                nums.pop_back();
                return ans;
            }
            return ans+1;
        }
  
        int removeElement(vector<int>& nums, int val) {
            if(nums.size()==0){
                return 0;
            }
            int output = helper(nums,val,0,nums.size()-1);
            return output;
        }
    };
  

• Optimized solution:

    class Solution {
    public:
  
        int removeElement(vector<int>& nums, int val) {
            int count = 0;
            for(int i=0; i<nums.length; i++){
                if(nums[i]==val){
                    continue;
                }
                nums[count] = nums[i];
                count++;
            }
            return count;
        }
    };
  

  I saw this solution in blog.devgenius.io and I realized that my recursive solution would have been the best choice if it was given that the order of number should be the same. But as it was mentioned that the order of numbers doesn't matter so we just have to shift the elements in the front and just return the count of numbers other than the number which was told to be removed.

1. Find the Index of the First Occurrence in a String

My approach:

I tried my best but couldn't come up with the O(n) solution. However, I was able to do it in the O(n^2) time. But later I learned a better solution as well.

My Solution:

• Brute Force :

    class Solution {
    public:
        int strStr(string haystack, string needle) {
            int ans = -1;
            bool isPresent = false;
            int count = 0;
  
            for(int i=0;i<haystack.length();i++){
                for(int j=0;j<needle.length();j++){
                    if(haystack[j+i]==needle[j]){
                        count++;
                        ans = i;
                    } else{
                        ans = -1;
                        count = 0;
                        break;
                    }
                }
                if(count==needle.length()){
                    break;
                }
            }
            return ans;
        }
    };
  

• Optimized solution:

    class Solution {
    public:
        int strStr(string haystack, string needle) {
  
            int m = haystack.length();
            int n = needle.length();
  
            for(int i=0;i<m-n+1;i++){
                if(haystack.substr(i,n)==needle){
                    return i;
                }
            }
            return -1;
        }
    };
  

  I saw the solution at https://walkccc.me/LeetCode/problems/0028/ and realized it was a very easy question I just have to think of using substring and when it said the first occurrence I should have just returned within the for loop.