*2, 3, 5, 6, 11, 14, 15,
Basics – Hash, Sort, XOR, Array element as index, Simple traversal
- 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
Algo: We can use sorting to do it in O(nLogn) time. We can also use hashing, it has the worst case time complexity of O(n), but requires extra space.
- ***** 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, find the nearest smaller number for every element such that the smaller element is on left side. GFG
- 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. O(n^2)
- 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))
– We compare middle element with its neighbour. Check the middle element.
– If the middle element is greater than its left neighbour, then there is always a local minima in left half (Why? take few examples).
– If the middle element is greater than its right neighbour, then there is always a local minima in right half (due to same reason as left half).
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
** 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 separate all 0 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.
- [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 .
Both the problem can be solved using a single approach
SO. There are two cases:
- The sum from indices 0 to
nis the number we’re looking for.
cur_sumis the running sum of all the indices, so it’s as easy as just checking that variable.
- The sum from indices
nis the number we’re looking for. If that is the case, then there exists an
msuch that the (sum from 0 to
n) minus (sum from 0 to
m) is the sum we’re looking for. All those intermediate sums are stored in the map, so that’s why we’re looking for
cur_sum - sum– if that difference corresponds to some partial sum, then we’re done.
Same: Find if there is a subarray with 0 sum
- The sum from indices 0 to
- 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)
The optimal size of a block to be jumped is O(√ n). This makes the time complexity of Jump Search O(√ n).The time complexity of Jump Search is between Linear Search ( ( O(n) ) and Binary Search ( O (Log n) ). Once found, the range, do a linear search within the range.