Array I | Striver’s SDE Sheet
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) $
Optimal
Use three variable pointing to and
Time Complexity: $ O(n) $
Auxiliary Space: $ O(1) $
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) $
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) $
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) $
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) $
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) $
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) $
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) $
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) $
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. {: .prompt-warning }
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. {: .prompt-tip }
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
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
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
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
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;
}
};