DEV Community: Mayank Arora

206. Reverse Linked List[Leetcode][C++]

Mayank Arora — Fri, 05 Aug 2022 04:07:00 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 206. Reverse Linked List

Using Recursion:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode *ptr=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        head=ptr;
        return head;
    }
};

Using Iteration:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev=NULL, *curr=head, *next=NULL;
        while(curr){
            next=curr->next;
            curr->next=prev;
            prev=curr;
            curr=next;
        }
        head=prev;
        return head;
    }
};

All suggestions are welcome. Please upvote if you like it. Thank you.

Source: Leetcode premium solution editorial

1936. Add Minimum Number of Rungs [Leetcode][C++]

Mayank Arora — Fri, 24 Dec 2021 02:01:00 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 1936. Add Minimum Number of Rungs

Input
rungs = [6,12,13,14,15], dist = 2
Output = 4

Ladder
---15
---14
---13
---12
---11
---10
---9
---8
---7
---6
---5
---4
---3
---2
---1
---0

Efficient Solution:
Concept of count1=(rungs[i]-rungs[i-1]-1)/dist vs count2=(rungs[i]-rungs[i-1])/dist
For example : If i=2, count1=(12-6)/2=3 & count2=(12-6-1)/2=2. From ladder diagram, if we add rungs at 8 & 10, it will enable us to climb from 6 to 12 in steps of 8-6=2=dist, 10-8=2=dist, 12-10=2=dist by adding minimum number of rungs. Hence, count2 is the correct equation.

class Solution {
public:
    int addRungs(vector<int>& rungs, int dist) {
        // Efficient Solution Time O(N) & Auxiliary Space O(1)
        int len=rungs.size();
        int count=(rungs[0]-1)/dist; 
        if(len==1)
            return count;
        for(int i=1;i<len;i++){
            count+=(rungs[i]-rungs[i-1]-1)/dist;
        }
      return count;
    }
};

All suggestions are welcome. Please upvote if you like it. Thank you.

1480. Running Sum of 1d Array [Leetcode][C++]

Mayank Arora — Fri, 24 Dec 2021 01:56:38 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 1480. Running Sum of 1d Array

Brute Force Solution:

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
    // Brute Force Solution Time O(N^2) & Auxiliary Space O(1)
    vector<int> result;
    int len=nums.size(),sum=0;
    for(int i=0;i<len;i++){
          sum=0;
        for(int j=0;j<=i;j++){
              sum+=nums[j];
        }
        result.push_back(sum);
    }
        return result;
    }
};

Efficient Solution:

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
    // Optimal Solution Time O(N) & Auxiliary Space O(1)
    int len=nums.size();
    for(int i=1;i<len;i++){
        nums[i]+=nums[i-1];
    }
        return nums;  
    }
};

All suggestions are welcome. Please upvote if you like it. Thank you.

Source: Leetcode premium solution editorial

977. Squares of a Sorted Array [Leetcode][C++]

Mayank Arora — Fri, 24 Dec 2021 01:54:50 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 977. Squares of a Sorted Array

Brute Force Solution:

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
       // Brute Force Solution Time O(NlogN) & Auxiliary Space O(1)
       int len=nums.size();
        for(int i=0;i<len;i++)
            nums[i]=nums[i]*nums[i];
        sort(nums.begin(),nums.end());
        return nums;
    }
};

Efficient Solution:

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        // Efficient Solution Time O(N) & Auxiliary Space O(1)
        // Two Pointer Method
        int len=nums.size(), lt=0, rt=len;
        vector<int> res;
        // Find index of first positive vector element & position right pointer
        for(int i=0;i<len;i++){
            if(nums[i]>=0){
                rt=i;
                break;
            }
        }
        // Position left pointer at smallest negative vector element
        lt=rt-1;
        while(lt>=0 && rt<=len-1){
        // Compare elements at left & right index and push the square of  
        // the smaller element in the resultant vector in ascending order
        // and reposition the left(decrement) & right(increment) pointers
            if(abs(nums[lt])<nums[rt]){
                res.push_back(nums[lt]*nums[lt]);
                lt--;
            }
            else if(abs(nums[lt])>nums[rt]){
                res.push_back(nums[rt]*nums[rt]);
                rt++;
            }
            else{
                res.push_back(nums[lt]*nums[lt]);
                lt--;
                res.push_back(nums[rt]*nums[rt]);
                rt++;
            }  
        }
        // Push the square of the element in the resultant vector for the
        // case of unvisited elements
        while(lt>-1){
              res.push_back(nums[lt]*nums[lt]);
              lt--;
            } 
        while(rt<len){
              res.push_back(nums[rt]*nums[rt]);
              rt++;
            }
        return res;
    }
};

All suggestions are welcome. Please upvote if you like it. Thank you.

Source: Leetcode premium solution editorial

509. Fibonacci Number [Leetcode][C++]

Mayank Arora — Fri, 24 Dec 2021 01:49:05 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 509. Fibonacci Number

Brute Force Solution:
For n=5, there are (2^(n-1))-1=15 recursive calls which leads to Time O(2^N) & Auxiliary Space O(1)

class Solution {
public:
    int fib(int n) {
    // Brute Force Solution
    if(n==0 || n==1){
        return n;
    }
    return fib(n-1) + fib(n-2);
    }
};

Efficient Solution(Dynamic Programming Bottom Up Approach):
Using sum vector to store intermediate fibonacci numbers computed in order to avoid redundant calculations. Time O(N) & Auxiliary Space O(N)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target){      
        //Efficient Solution TimeO(N) & Auxiliary Space O(N)
        int length=nums.size();
        unordered_map<int,int> map;
        for(auto i=0;i<length;i++){
            if(map.find(target-nums[i])!=map.end()){
                return {i,map[target-nums[i]]};
        }
        map[nums[i]]=i;
        }
        return {};
    }
};

Efficient Solution(Dynamic Programming Bottom Up Approach(Storing the two most recent intermediate fibonacci numbers calculated):
Time O(N) & Auxiliary Space O(1)

class Solution {
public:
    int fib(int n) {
    // Efficient Solution
    if(n==0 || n==1){
            return n;
    }
    int f_minus_1 = 0, f = 1;
    for(int i = 2; i <= n; i++){
        f = f + f_minus_1;
        f_minus_1 = f - f_minus_1;
    }
    return f;
    }
};

Efficient Solution(Matrix Multiplication & Binary Exponentiation):
Time is O(logN) & Auxiliary Space O(logN) due to recursive stack calls in power() function

// Matrix mulplication
/*
| fib(n) |   |1  1|   |fib(n-1)|
|        | = |    | * |        |    
|fib(n-1)|   |1  0|   |fib(n-2)|

For n=2,

|fib(2)|   |1  1|   |fib(1)| 
|      | = |    | * |      |        
|fib(1)|   |1  0|   |fib(0)|

For n=3,

|fib(3)|   |1  1|^2     |fib(1)| 
|      | = |    |   *   |      |      
|fib(2)|   |1  0|       |fib(0)|

General Expression :

| fib(n) |   |1  1|^(n-1)        |fib(1)=1|
|        | = |    |       *      |        |
|fib(n-1)|   |1  0|              |fib(0)=0|
*/
class Solution {
public:
    void mul(int A[2][2], int B[2][2])
    {
            // Multiplying 2x2 matrices in time O(1)
            int A00 = (A[0][0] * B[0][0]) + (A[0][1] * B[1][0]);
            int A01 = (A[0][0] * B[0][1]) + (A[0][1] * B[1][1]);
            int A10 = (A[1][0] * B[0][0]) + (A[1][1] * B[1][0]);
            int A11 = (A[1][0] * B[0][1]) + (A[1][1] * B[1][1]);
            A[0][0] = A00; A[0][1] = A01; A[1][0] = A10; A[1][1] = A11;
        }
    void power(int A[2][2], int exp)
    {
        // Calculates matrix multiplication using binary exponentiation in time O(logN)
        // A^x=A^(x/2) * A^(x/2), if x is even
        // A^x=A * A^(x/2) * A^(x/2), if x is odd
        int B[2][2] = { {1,1} , {1,0} };
        if(exp == 0 || exp == 1) 
            return;
        power(A, exp/2);
        mul(A, A);
        if(exp%2!=0) 
        mul(A, B);
    }
    int fib(int n)
    {
    // Efficient Solution
    int A[2][2] = { {1,1} , {1,0} };
    if(n == 0) 
            return 0;
    power(A, n-1);
    // A[0][0] is the required nth fibonacci number 
    return A[0][0]; 
    }
};

Optimal Solution(Binet's Formula):
Time O(1) & Auxiliary Space O(1)

class Solution {
public:
    int fib(int n) {
    // Optimal Solution
    // The formula is true for all n but works till n=70 in C++ implementation
    // due to approximations in computations & range limits of data types.
    // Double data type ensures high precision and correct answer till n=70
    double z = sqrt(5);
    double t = (pow(2,n)*z);
    double a = (pow(1+z,n));
    double b = (pow(1-z,n));
    cout<<fixed; // Converts scientific notation to fixed-point notation
    cout<<round((a-b)/t); // Rounds off the decimals and replaces them with 0's
    }
};

All suggestions are welcome. Please upvote if you like it. Thank you.

Source: Leetcode premium solution editorial

724. Find Pivot Index [Leetcode][C++]

Mayank Arora — Fri, 24 Dec 2021 01:42:11 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 724. Find Pivot Index

Brute Force Solution:

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
    // Brute Force Solution Time O(N^2) & Auxiliary Space O(1)
    // Calculate the sum of elements to the left & right
    // of each index of nums vector and compare them to check equivalence
    int len=nums.size();
    if(len==1)
        return nums[0];
    for(int i=0;i<len;i++){
         // accumulate() takes O(N) time and for loop runs for n iterations.
         // So time taken by for loop is O(n*n)=O(N^2)
          int left=accumulate(nums.begin(),nums.begin()+i,0); 
          int right=accumulate(nums.begin()+i+1,nums.end(),0);
          if(left==right)
              return i;
    }
      return -1;
    }
};

Efficient Solution:

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
    // Efficient Solution Time O(N) & Auxiliary Space O(1)
    // Create a sum array in which each element stores 
    // the sum of elements of nums vector up to that index.
    // Calculate left & right sum. For example-
    // nums[]=[1,7,3,6,5,6]
    // sum[]= [1,8,11,17,22,28]
    // left[3]=17-6=11
    // right[3]=28-17=11
    // return 3
    int len=nums.size();
    if(len==1)
        return 0;
    int sum[len];
    sum[0]=nums[0];
    for(int i=1;i<len;i++){
        sum[i]=nums[i]+sum[i-1];
    }
    for(int i=0;i<len;i++)
    {
        int left=sum[i]-nums[i];
        int right=sum[len-1]-sum[i];

    if(left==right)
        return i;
    }
      return -1;
    }
};

All suggestions are welcome. Please upvote if you like it. Thank you.

Source: Leetcode premium solution editorial

560. Subarray Sum Equals K [Leetcode][C++]

Mayank Arora — Fri, 24 Dec 2021 01:39:56 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 560. Subarray Sum Equals K

Brute Force Solution:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // Brute Force Solution Time O(N^3) & Auxiliary Space O(1)
        // Time Limit Exceed(TLE) 61/89 test cases passed
        int len=nums.size(),count=0;
        // Consider all possible subarrays
        for(int i=0;i<len;i++){ 
            for(int j=i;j<len;j++){ // Consider subarray from nums[i] to nums[j]
                int sum=0;
                for(int s=i;s<=j;s++){ // Calculate sum of elements from nums[i] to nums[j]
                   sum+=nums[s]; 
        }
                if(sum==k) // Check if sum is equal to k
                    count++;
        }
        }
        return count;
    }
};

Better Solution:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // Better Solution Time O(N^2) & Auxiliary Space O(N)
        // Time Limit Exceed(TLE) 84/89 test cases passed
        int len=nums.size(), count=0;
        vector<int> ls; // prefix sum array or left sum array
                        // ls[i] will be sum of elemensts from nums[0] to nums[i]
        ls.push_back(0);
        for(int i=0;i<len;i++)
            ls.push_back(ls.back()+nums[i]); // inserting elements in ls
        for(int i=0;i<ls.size();i++){ 
            for(int j=i+1;j<ls.size();j++){ 
                   // For example: nums[]={2,8,5,-3,1,8}, k=10
                   // ls[]={2,10,15,12,13,21}, k=10
                   // nums[1]+nums[2]+nums[3]=8+5+(-3)=10. 
                   // j runs from 1 to 3. For j=i+1 & j=1, we get i=0.
                   // Therefore i=0 & j=3.
                   // ls[j=3]-ls[i=0]=12-2=10 which is equal to k.
                   if(ls[j]-ls[i]==k) 
                       count++;
            }
        }
        return count;
    }
};

Optimal Solution:

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // Optimal Solution Time O(N) & Auxiliary Space O(N)
        int ls=0; // ls is left sum variable or prefix sum variable 
                  // whose value on nums[] traversal is the sum of nums[i] and  
                  // all the elements that came before it(nums[i-1], nums[i-2]. nums[i-3],.......nums[0])
        int len=nums.size(), count=0; 
        map<int,int> m; // m is a map that maps ls value to its frequency 
                        // of occurence as m[key,value]={ls,frequency}
        m[0]=1;      // If k=0, then subarray with no elements is also a subset of nums and sum of 
                     // empty subarray elements is zero. So, number of subarrays with k(=0) sum has count 
                     // of 1 initially. If k is non zero, then ls-k=0 which means ls is equal to k. 
                     // It means that for a certain index i in nums[i], the sum 
                     // nums[0]+nums[1]+numns[2]......nums[i] is equal to k. 
                     // m[0]=1 is included in count if k=0 or ls-k=0.
        for(int i=0;i<len;i++){
            ls+=nums[i];
            /*
            m[0] = 1

     i  |  ls  |     m      |   m[ls-k]    | count
     ---|------|------------|--------------|-------
     0  |  1   |  m[ 1] = 1 | m[ 1-  8 ]=0 |  0
     1  |  8   |  m[ 8] = 1 | m[ 8-  8 ]=1 |  1
     2  |  14  |  m[14] = 1 | m[14 - 8 ]=0 |  1
     3  |  16  |  m[16] = 1 | m[16 - 8 ]=1 |  2
     4  |  19  |  m[19] = 1 | m[19 - 8 ]=0 |  2
     5  |  22  |  m[22] = 1 | m[22 - 8 ]=1 |  3
     6  |  24  |  m[24] = 1 | m[24 - 8 ]=1 |  4

   nums[]=[1, 7,  6,  2,  3,  3,  2 ]     
       i = 0, 1,  2,  3,  4,  5,  6 
ls value = 1, 8, 14, 16, 19, 22, 24 
           x=ls-k       k=8     
        <----------><---------->
                 ls=22
        <---------------------->  
                */
            // If x=ls-k=22-8=14 has been the value of ls anytime before, then it means that 
            // ls-x=22-14 is k. Count will increment by number of times of x=ls-k occurence which
            // is stored in m[ls-k]
            count+=m[ls-k];
            m[ls]++; // Store the frequency of ls value in map
        }
        return count;
    }
};

All suggestions are welcome. Please upvote if you like it. Thank you.

Source: Leetcode premium solution editorial

283. Move Zeroes [Leetcode][C++]

Mayank Arora — Fri, 24 Dec 2021 01:36:02 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 283. Move Zeroes

Brute Force Solution:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
    // Brute Force Solution Time O(N) & Auxiliary Space O(N)
    vector<int> a;
    int count=0;
    for(int i=0;i<nums.size();i++){
        if(nums[i]==0)
            count++;
        else
            a.push_back(nums[i]);
    }
    while(count--)
        a.push_back(0);
    for(int i=0;i<nums.size();i++){
        nums[i]=a[i];
    } 
  }
};

Efficient Solution:

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
    // Efficient Solution Time O(N) & Auxiliary Space O(1)
    int lt=0,rt=0,n=nums.size();
    while(rt<n){
         if(nums[rt]==0)
              rt++;
         else{
              int temp=nums[lt];
              nums[lt]=nums[rt];
              nums[rt]=temp;
              lt++;
              rt++;
            }
        }
    }
};

All suggestions are welcome. Please upvote if you like it. Thank you.

Source: Leetcode premium solution editorial

169. Majority Element [Leetcode][C++]

Mayank Arora — Fri, 24 Dec 2021 01:33:33 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 169. Majority Element

Brute Force Solution : Time O(NlogN) & Auxiliary Space O(1)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // Brute Force Solution
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

Better Solution : Time O(N) & Auxiliary Space O(N)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // Better Solution
        map<int,int> m;
        int len=nums.size(), pos;
        for(int i=0;i<len;i++){
            m[nums[i]]++;
        if(m[nums[i]]>(len/2))
            pos=i;
        }
        return nums[pos];
    }
};

Optimal Solution : Time O(N) & Auxiliary Space O(1)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // Optimal Solution
        // Boyer–Moore Majority Voting Algorithm
        int len=nums.size(), maj=nums[0], count=1;
        for(auto i=1;i<len;i++){
            if(nums[i]==maj)
                count++;
            else
                count--;
            if(count==0){
                maj=nums[i];
                count=1;
            }
        }
        return maj;
    }
};

All suggestions are welcome. Please upvote if you like it. Thank you.

Source: Leetcode premium solution editorial

122. Best Time to Buy and Sell Stock II [Leetcode][C++]

Mayank Arora — Fri, 24 Dec 2021 01:23:45 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 122. Best Time to Buy and Sell Stock II

e.g. Array=[7,1,5,3,6,4]

Valley to Peak approach : Add all gains from positive slopes i.e. profit = (5-1) + (6-3) = 7

Efficient Solution:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // Optimal Solution Time O(N) & Auxiliary Space O(1)
        int res = 0;
        for (int i = 1; i < prices.size(); ++i)
            res += max(prices[i] - prices[i - 1], 0);
        return res;
    }
};

All suggestions are welcome. Please upvote if you like it. Thank you.

Source: Leetcode premium solution editorial

121. Best Time to Buy and Sell Stock [Leetcode][C++]

Mayank Arora — Fri, 24 Dec 2021 01:18:27 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 121. Best Time to Buy and Sell Stock

Brute Force Solution:

class Solution {
public:
    int maxProfit(vector<int>& prices) { 
    // Brute Force Solution Time O(N^2) & Auxiliary Space O(1)
    int len=prices.size(),profit=0;
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(prices[j]>prices[i]){
                    int pro=prices[j]-prices[i];
                    profit=max(profit,pro);
                }
            }
        }
    return profit; 
  }
};

Efficient Solution:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    // Efficient Solution Time O(N) & Auxiliary Space O(1)
    int min_val=INT_MAX,profit=0,len=prices.size();
    for(int i=0;i<len;i++){
          min_val=min(min_val,prices[i]);
          profit=max(profit,prices[i]-min_val);
        }
    return profit;
    }
};

All suggestions are welcome. Please upvote if you like it. Thank you.

Source: Leetcode premium solution editorial

118. Pascal's Triangle [Leetcode][C++]

Mayank Arora — Fri, 24 Dec 2021 01:16:29 +0000

All suggestions are welcome. Please upvote if you like it. Thank you.

Leetcode Problem Link: 118. Pascal's Triangle

Brute Force Solution:

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
    // Brute Force Solution Time O(N^2) & Auxiliary Space O(1)
    vector<vector<int>> ret(numRows);
    for (int i = 0; i < numRows; i++) {
    ret[i].resize(i+1); // Resize number of elements in each row from from numRows to i+1 
        ret[i][0]=1; ret[i][i]=1; // Put 1's at first & last element of each row
    for (int j = 1; j < i; j++) {
        // Assigning element values in row from second element to second last element
        // by adding corresponding jth & (j-1)th element in previous row
        // as shown in question animation
        ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
    }
    }
    return ret;
}
};

All suggestions are welcome. Please upvote if you like it. Thank you.

Source: Leetcode premium solution editorial