Home Day 1 Array | Striver 180 | takeUforward
Post
Cancel

Day 1 Array | Striver 180 | takeUforward

Problem 1

Find the duplicate in an array of N+1 integers.

Worst

Just apply mergesort

Time Complexity: $ O(nlogn) $

Auxiliary Space: $ O(n) $

Better

Count the occurences of 0,1,2 in first transversal and update the array in the second.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(1) $

1

Optimal

Use three variable pointing to and

Time Complexity: $ O(n) $

Auxiliary Space: $ O(1) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low=0,high=nums.size()-1,mid=0;
        while(mid<=high){
            if(nums[mid]==0){
                swap(nums[mid],nums[low]);
                mid++;
                low++;
            }
            else if(nums[mid]==1){
                mid++;
            }
            else{
                swap(nums[high], nums[mid]);
                high--;
            }
        }
    }
};

Problem 2

Sort an array of 0’s 1’s 2’s without using extra space or sorting algo

Worst

Just apply mergesort

Time Complexity: $ O(nlogn) $

Auxiliary Space: $ O(n) $

Better

Count the occurences of 0,1,2 in first transversal and update the array in the second.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(1) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution
{
public:
    void sort012(int a[], int n)
    {
        int zeros = 0, ones = 0, twos = 0;
        for (int i = 0; i < n; i++)
        {
            if (a[i] == 0)
            {
                zeros++;
            }
            else if (a[i] == 1)
            {
                ones++;
            }
            else
            {
                twos++;
            }
        }
        int i = 0;
        while (zeros > 0)
        {
            a[i++] = 0;
            zeros--;
        }
        while (ones > 0)
        {
            a[i++] = 1;
            ones--;
        }
        while (twos > 0)
        {
            a[i++] = 2;
            twos--;
        }
    }
};

Optimal

Use three variable pointing to and

Time Complexity: $ O(n) $

Auxiliary Space: $ O(1) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low=0,high=nums.size()-1,mid=0;
        while(mid<=high){
            if(nums[mid]==0){
                swap(nums[mid],nums[low]);
                mid++;
                low++;
            }
            else if(nums[mid]==1){
                mid++;
            }
            else{
                swap(nums[high], nums[mid]);
                high--;
            }
        }
        
    }
};

Problem 3

Find the repeating and the missing number.

Worst

Apply mergesort and then find the missing and repeating value.

Time Complexity: $ O(nlogn) $

Auxiliary Space: $ O(n) $

Better

Use a hash array or hash map to count the occurrences of numbers.Index with values ‘2’ and ‘0’ will give the repeating and missing numbers respectively.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(n) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution
{
public:
    int *findTwoElement(int *arr, int n)
    {

        static int ar[2];
        int index[n] = {0};

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

        for (int i = 0; i < n; i++)
        {
            if (index[i] > 1)
            {
                ar[0] = i + 1;
            }
            if (index[i] < 1)
            {
                ar[1] = i + 1;
            }
        }

        return ar;
    }
};

Better

Use three variable pointing to and

Time Complexity: $ O(n) $

Auxiliary Space: $ O(1) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
public:
    int *findTwoElement(int *arr, int n) {
    
    static int ar[2];  
    for (int i = 0; i < n; i++)
        if (arr[abs(arr[i]) - 1] > 0)
            arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1];
        else
            ar[0] = abs(arr[i]) ;
    
 
    for (int i = 0; i < n; i++) 
        if (arr[i] > 0)
            ar[1] = (i + 1);
    
    return ar;
    }
};

Optimal

Use three variable pointing to and

Time Complexity: $ O(n) $

Auxiliary Space: $ O(1) $

1
2
3
4
5
6
7
class Solution{
public:
    int *findTwoElement(int *arr, int n) {
    
    
    }
};

Problem 4

Worst

Swap all the smaller numbers from the second array and then sort both the resultant arrays.

Time Complexity: $ O(nlogn) $

Auxiliary Space: $ O(n) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution{
    public:
        //Function to merge the arrays.
        void merge(long long arr1[], long long arr2[], int n, int m) 
        { 
            
        int i=n-1, j = 0;
        while(i>=0 && j<m)
        { 
        if(arr1[i] > arr2[j])
        swap(arr1[i--] , arr2[j++]);
        else
        i--;
        }
        
        sort(arr1 , arr1+n);
        sort(arr2 , arr2+m);
        
        } 
};

Better

Use inserstion sort.

Time Complexity: $ O(n) $

Auxiliary Space: $ O(n) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution
{
public:
    int *findTwoElement(int *arr, int n)
    {

        static int ar[2];
        int index[n] = {0};

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

        for (int i = 0; i < n; i++)
        {
            if (index[i] > 1)
            {
                ar[0] = i + 1;
            }
            if (index[i] < 1)
            {
                ar[1] = i + 1;
            }
        }

        return ar;
    }
};

Optimal

Use three variable pointing to and

Time Complexity: $ O(n) $

Auxiliary Space: $ O(1) $

1
2
3
4
5
6
7
class Solution{
public:
    int *findTwoElement(int *arr, int n) {
    
    
    }
};

5. Maximum Subarray

Given an integer array arr, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum and print the subarray.

A subarray is a contiguous part of an array.

Naive

  • Practice

    Use two loops to get generate all the subarrays and then store the sum of a subarray in a variable. Return the max value.

Time Complexity: $ O(n^2) $ Auxiliary Space: $ O(1) $

Optimal

Implement Kadane Algorithm. Declare two variables: local sum and maximum sum. Iterate the array, adding the elements to the local sum. Update ans when ans is greater than sum.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum =0, mx = INT_MIN;
        for (int i=0; i< nums.size(); i++){
            sum += nums[i];
            mx = max(sum ,mx);
            if (sum < 0)
                sum = 0;
        }
        return mx;
    }
};

Time Complexity: $ O(n) $ Auxiliary Space: $ O(1) $

6. Stocks Sell or Buy

Brute

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution
{
public:
    void maxProfit(vector<int>& prices)
  {
          for (int i = 0; i < prices.size() - 1; i++) {
            for (int j = i + 1; j < prices.size(); j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxprofit)
                    maxprofit = profit;
            }
        }
        return maxprofit;
  }
};

Optimal

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy = INT_MAX, n =  prices.size(), profit = 0;
        for (auto price : prices)
        {
            if (price < buy) buy = price;
            if (price - buy > profit) profit = price - buy;
        }
        return profit;
    }
};

Day 8 | Greedy

Day 9 | Recursion

Subset Sums

Given a list arr of N integers, print sums of all subsets in it.

Note: Return all the element is increasing order.

Brute

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
public:

    vector<int> subsetSums(vector<int> arr, int N)
    {
        vector<int> ans;
        long long total = 1 << n;
    
        for (long long i = 0; i < total; i++) {
            long long sum = 0;
            for (int j = 0; j < n; j++)
                if (i & (1 << j))
                    sum += arr[j];
    
            ans.push_back(sum);
            sort(ans.begin(), ans.end());
            return ans;
        }
};

Optimal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:

    void solve(int index, int sum, int N, vector<int> &arr, vector<int> &ans)
    {
        if(index == N){
            ans.push_back(sum);
            return;
        }
        
        solve(index+1, sum + arr[index], N, arr, ans);
        solve(index+1, sum, N, arr, ans);
    }

    vector<int> subsetSums(vector<int> arr, int N)
    {
        vector<int> ans;
        solve(0, 0, N, arr, ans);
        sort(ans.begin(), ans.end());
        return ans;
    }
};

Day 15 | String

Day 21 | Binary Search Tree Part-II

This post is licensed under CC BY 4.0 by the author.

August | 2022 | Leetcoding Challenge

-