- [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. Algo –
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 . 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.
We can’t apply binary search as we don’t know the size of the array. 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. 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. GFG
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
1. Traverse the array. O(n)
**2. Use Binary Search. O(log(n))
Start a while loop. Check if the mid element is minima. If mid -1 < mid, then there exists a minima on the left(take few examples and see). Start searching the left half else search the right 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.
Code. Bye-by-byte Complexity: O(m + n). Algo –
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)
While searching for the element in the row since the values are sorted, we can use binary search. So complexity will reduce but the overall complexity remains the same.
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. Youtube
- Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s. GFG.
Algo: We do a binary search in each row to get a count of 1 in each row. Time Complexity: O(mLogn)
Complexity – since we lookup for a number in all the row and not in a single row, so complexity O(mlogn) and not O(m+n).
We use binary search to find the first index of 1 in each row.
- 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.
Algo: XOR Time Complexity is O(n). Asked in: Amazon, Microsoft
- Given an array of integers, sort the array into a wave like array and return it. GFG
Given [1, 2, 3, 4]
One possible answer : [2, 1, 4, 3]
Another possible answer : [4, 1, 3, 2]
Algo: Asked in Amazon, Goldman Sachs, Paytm
Approach 1: First sort the input array, then swap all adjacent elements. O(nLogn)
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.
- 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.
- [Hashing] Find the largest subarray with 0 sum. Given an array of integers, find length of the largest subarray with sum equals to 0. GFG.
- Given an array of integers and a number k, find maximum sum of a subarray of size k. GFG.
Algo: 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)