Basics – Hash, Sort, XOR, Array element as index, Simple traversal
- [SKIP] Find the element that appears once Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. Expected time complexity is O(n) and O(1) extra space. GFS
- *** Find a sorted subsequence of size 3 in linear time Given an array of n integers, find the 3 elements such that a[i] < a[j] < a[k] and i < j < k in 0(n) time. If there are multiple such triplets, then print any one of them. GFG. Amazon.
We create two array.
The first array maintains the index of the element smaller than the current index.
The second array maintains the index of the element greater than the current index.
Now if we consider an index i, in both the array simultaneously, it gives the index of element smaller then that index i and index of element greater than that index i. So that value i lies b/w the smaller and greater index.
- Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2. GFS .
Algo: Sort and the use the logic of 3 sum problem.
- Given an input array of size unknown with all 1’s in the beginning and 0’s in the end. find the index in the array from where 0’s start. consider there are millions of 1’s and 0’s in the array.i.e array is very big..e.g array contents 1111111…….1100000………0000000. Career Cup.
1. We can’t apply binary search as we don’t know the size of the array.
2. Jump Search. We can start inquiring the the numbers at indices at 2, 4, 8, … till we find a 1 at say 2^(n-1) and a 0 at 2^n. Now we can do binary search between these two indices for 0.
3. We can’t use XOR here. Try to consider that case when there are odd 1 and when there are even 1 in the input.
- ** Find the local minima in an array.
We say that an element arr[x] is a local minimum if it is less than or equal to both its neighbors. For corner elements, we need to consider only one neighbor for comparison.There can be more than one local minima in an array, we need to find any one of them. Youtube Code. GFG .
1. Traverse the array. O(n)
**2. Use Binary Search. O(log(n))
An efficient solution is based on Binary Search. We compare middle element with its neighbors. If middle element is not greater than any of its neighbors, then we return it. If the middle element is greater than its left neighbor, then there is always a local minima in left half (Why? take few examples). If the middle element is greater than its right neighbor, then there is always a local minima in right half (due to same reason as left half).
The break condition – if mid – 1 > mid && mid < mid +1 –
>here we also need to take care of the condition that the mid is not the first or last element in the array.
So adding those condition as well –
((mid == 0 || a[mid – 1] >= a[mid]) && (mid == n – 1 || a[mid] <= a[mid + 1]))
Similar: Find a peak element Code
Both the approach are same.
- *** Search in a row wise and column wise sorted matrix. OR
Given an array of NxN matrix find a number e in linear time, the array satifies the following condition: A[i][j] < A[i+1][j], A[i][j] < A[i][j+1], A[i][j] < A[i-1][j] and A[i][j] < A[i][j-1]. This is asked in many top companies.
Approach 1: We pick up the last element of first row. Then compare it. If key is smaller then it might be present in the same row. So now we search in the current row, and keep changing column keeping row constant. If the key is bigger we move to the last element of the next row and repeat the same process.
Complexity – Since we lookup for a number only in a row and not in all rows, so complexity O(m+n) and not O(mn). Youtube
Approach 2: We pick the first and last element of a row. If the key lies in that range that we do a binary search in that row. Else move to the next row and do the same check. Complexity is same for this approach also.
** Similar: In this case we have positive and negative elements in the row and column wise sorted matrix. We need to find the count of negative number.
Count Negative Integers in Row/Column-Wise Sorted Matrix .
We use the approach 1. We start with the top right element. Now we find the negative element in that row. The thing to note here is that in next row we don’t need to start at the last element. We can start just below the last negative element from the previous row.
- ** Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s. GFG.
1. We do a binary search in each row to get a count of 1 in each row.
Time Complexity: O(mLogn)
2. Get the index of first (or leftmost) 1 in the first row. Do following for every row after the first row
…IF the element on left of previous leftmost 1 is 0, ignore this row.
…ELSE Move left until a 0 is found. Update the leftmost index to this index and max_row_index to be the current row. O(m+n)
- Seprate even and odd numbers in an array OR
In an unsorted of only 0’s and 1’s seprate all o on the left and all 1 on the right –
Algo: Use two pointers, one at the starting and other at the end and check for the nos. to be exchanged. Asked in MakeMyTrip.
Time Complexity: O(n)
- Given two integer arrays where second array is duplicate of first array with just 1 element missing. Find the element. Link. Asked in: Amazon, Microsoft
Time Complexity is O(n).
- *** Given an array of integers, sort the array into a wave like array and return it. GFG. Asked in Amazon, Goldman Sachs, Paytm
Approach 1: First sort the input array, then swap all adjacent elements. O(nLogn). This is same we do in linked list.
Approach 2: Complexity = O(n)
The idea is based on the fact that if we make sure that all even positioned (at index 0, 2, 4, ..) elements are greater than their adjacent odd elements, we don’t need to worry about odd positioned element. Following are simple steps.
1) Traverse all even positioned elements of input array, and do following.
….a) If current element is smaller than previous odd element, swap previous and current.
….b) If current element is smaller than next odd element, swap next and current.
We want the element at even position to be larger then it’s neighbor.
So traverse the even position index. If the element is smaller then the previous odd, swap. If the element is smaller then the next odd, swap. So max two swap possible for each index.
- Find pair with greatest product in array. Given an array of n elements, the task is to find the greatest number such that it is product of two elements of given array. If no such element exists, print -1. GFS.
Algo: Use hash. Same as sum pair problem.
- [Binary Search] Ceil and floor in a sorted array Code
- *** Kadane Algorithm – Largest Sum Contiguous Subarray Code Youtube
The idea is simple. At each index of array we check if what’s the maximum subarray till now. The max subarray can be either the current-index-element alone or the sum previous subarray index + the current index.
At each index we check what’s the maximum subarray that we have found instead of storing the sum in another array.
import java.lang.*; -> to use the Math.max collection.
- *** Find the largest subarray with 0 sum. Given an array of integers, find length of the largest subarray with sum equals to 0. GFG.
Algo: Here will use hashing.
This is not similar to the this (Find subarray with given sum without negative).
Find subarray with given sum with negative numbers. GFG
- Given an array of integers and a number k, find maximum sum of a subarray of size k. GFG.
Algo: Sliding window concept. Time Complexity : O(n)
We have to find the number of element in size of window k. We don’t want to calculate the sum of element of window for every possible window. So we find the sum of first window and on adding new element we remove the first element of the window.
So we find the sum of all element of first window. Then start looping through the element after the window. Then add new element sum to window and remove the first one. At each element keep a track of maximum sum till now.
- Print 2-D array in spiral order. Youtube.
- *** Jump Search. GFG Works only sorted arrays.
best step to jump – √n
Time Complexity : O(√n)
Auxiliary Space : O(1)
useful when the array is sorted but there no end given or the data size is very big.