striver A2Z DSA
when a function calls itself until a specified condition is met. In direct recursion, function calls itself while in indirect recursion the function fun1 calls another function fun2 which calls the fun1 function.
A solve a problem using recursion we must know solution to a smaller problem and bigger problems are solved using this small problem. These small problems are the base cases which can be solved on their own.
returnType functionName(parameters){
base_case {
operations to be performed on base case
}
// perform some operation
call for smaller problem
functionName(smaller Parameter)
}
Sort the given array and return the value of last element for largest and first element for smallest.
sort(arr,arr+n);//step 1: sort
return arr[n-1]; //step 2: return last element
Take first element as largest/smallest. Traverse the array and update the largest/smallest variable when a greater/smaller element is found. Return variable largest/smallest.
int largest = arr[0];
for(int i =0; i<n;i++){
largest = max(largest,arr[i]);//for smallest take min of two
}
return largest;
Return the Second Largest/smallest element from an array.
Sort the array. Traverse the array from back and return the first element which is not equal to largest i.e last element of the array. there may be a condition possible that all the elements in the array are largest and hence there wont be any second largest in the array. and we may have to traverse the whole array.
sort(arr,arr+n);//step 1: sort O(Nlogn)
for(int i=n-2; i>=0; i--){//traverse from last //O(N)
if(arr[i]!=arr[n-1]){//find the first unequal element
return arr[i];
}
}
return -1;
//O(NlogN+N)
First find the largest element from the array. Traverse the array from starting and find the largest element in the array except the first largest element.
int largest = arr[0];
int secondLargest = INT_MIN;
for(int i =0; i<n;i++){
largest = max(largest,arr[i]);//find the largest
}
for(int i =0; i<n;i++){
if(arr[i]!=largest){//find largest element except first
secondLargest = max(secondLargest,arr[i]);
}
}
return secondLargest;
Intution: If current largest is updated than previous largest becomes second largest and largest gets updated. When element smaller than largest but greater than secondLargest is encountered than only second largest is updated.
We first set largest and second largest to INT_MIN. Then We traverse the array and if any element greater than largest is found we simply update secondLargest = largest and largest = that element. If an element is not equal to and smaller than largest but greater than secondLargest then we update second largest.
int secondLargest(int arr[], int n){
int first = -1;
int second = -1;
for(int i =0; i<n; i++){
if(first<arr[i]){
second = first;
first =arr[i];
}else if(arr[i]!=first && second<arr[i]){
second = arr[i];
}
}
return second;
}
//O(N)
Check if the array is in non-decreasing order if yes then return true else false.
Traverse array and return false for wrong order.
Traverse the array from i=1 and check if any a[i-1]>a[i] then return false else after traversing whole array return true
bool checkSorted(int arr[], int n){
for(int i=1; i<n; i++){
if(arr[i]<arr[i-1]){
return false;
}
}
return true;
}
//O(N)
Your are Given a sorted array containing duplicates you have to remove the duplicates from this array.
Set is an stl in c++ that only stores unique elements. its t.c for insertion is O(logn) Approach: traverse the array and insert elements into a set this set will be containing only unique elements. Copy this set into the array
int removeDuplicates(vector<int> &arr, int n) {
set<int> s;
for(int i =0; i<n; i++){
if(s.count(arr[i])==0){
s.insert(arr[i]);
}
}
int j=0;
for(auto it: s){
arr[j] = it;
j++;
}
return j;
}
Take two pointers i and j, where i points to the last element of the unique element array and j points to duplicate arrays first element. i.e i=0 and j=1 Traverse the duplicate array from 1 to n and check if arr[i] !=arr[j] then increment i and put arr[j] on it.
int removeDuplicates(vector<int> &arr, int n) {
int j=0;
for(int i=0; i<n-1; i++){
if(arr[i]==arr[i+1]){
continue;
}
arr[j++] = arr[i];
}
return j+1;
}
Store first element in a temp variable and move all values of array 1 index towards right. i.e a[i-1] = a[i] and store temp at a[n-1] that is last index.
vector<int> rotateArray(vector<int>& arr, int n) {
// Write your code here.
int temp = arr[0];
for(int i=1; i<n; i++){
arr[i-1] = arr[i];
}
arr[n-1] = temp ;
return arr;
}
Store last element in temp and traverse array from end till index 1 and move all elements one index ahead i.e. a[i] = a[i-1] and store temp at starting index.
vector<int> rotateArrayRight(vector<int>& arr, int n) {
// Write your code here.
int temp = arr[n-1];
for(int i=n-1; i>=1; i--){
arr[i] = arr[i-1];
}
arr[0] = temp ;
return arr;
}
after n rotations Array gets back to its original form. therefore k = k%n;
Left rotate by 1 the given array k times Time complexity : O(k*n) space complexity: O(1)
vector<int> rotateArray(vector<int> arr, int k) {
int n = arr.size();
for (int i = 0; i < k; i++) {
int temp = arr[0];
for (int j = 0; j < n - 1; j++) {
arr[j] = arr[j + 1];
}
arr[n - 1] = temp;
}
return arr;
}
Store the first k elements in the temp array. Now Move other elements by k times towards left Put the temp elements in the array after n-k elements
T.C. O(N) S.C. O(k)
vector<int> rotateArray(vector<int> arr, int k) {
int n = arr.size();
k= k%n;
int temp[k];
//copy first k elements to temp
for(int i =0; i<k ; i++){
temp[i] = arr[i];
}
//move other elements by k positions
for(int i =k; i<n; i++){
arr[i-k] = arr[i];
}
//copy temp elements to array from n-k to n
for(int i=n-k; i<n; i++){
arr[i] =temp[i-(n-k)];
}
return arr;
}
Reverse first k elements of array Reverse remaining elements of array Reverse the whole array
e.g. [1,2,3,4,5] k = 2 o/p = [3,4,5,1,2] reverse first k => [2,1,3,4,5] reverse remaining => [2,1,5,4,3] reverse whole array => [3,4,5,1,2] <= desired output
time complexity : O(N) space Complexity : O(1)
void reverse(vector<int> &arr, int s, int e){
while(s<e){
swap(arr[s],arr[e]);
s++;
e--;
}
}
vector<int> rotateArray(vector<int> arr, int k) {
reverse(arr,0,arr.size()-1);
reverse(arr,0,arr.size()-1-k);
reverse(arr,arr.size()-k, arr.size()-1);
return arr;
}