Array – Set 2 Array Set 3
Important -> 1 – 6, 9, 10, 11 -13, 20, 21, 23, 24
Binary Search -> 16, 21, 24, 25, 26, 27
More Array Problems – TR , InterviewBit
last set bit = a & ~(a-1)
counting number of set bit = while a > 0: a & (a-1)
General Direction For Thinking for Array Problem –
1. Brute force is the obvious one and should be instant response
2. Sorting (multiple pointers when sorting is also useful | sometimes search after sort )
3. Hash
When we are given condition like numbers are in range 1 to n, you should also think on line of using XOR, or using array element only as index. These question generally have a condition of using no extra space so we can use the same array and keep a count. Like using this approach we can find duplicates in O(n) time and O(1) extra space. These are a specific set of problem that revolve around the same concept.
One of the most common way to detect duplicate is Hash.
- *** Longest Consecutive Subsequence – Given an array of integers, find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.
Algo –1. Sorting and loop the array and ….Complexity = O(nLogn)
* 2. Hashing. Complexity: O(n)
1) Create an empty hash.
2) Insert all array elements to hash.
3) Do following for every element arr[i]
….a) Check if this element is the starting point of a subsequence. To check this, we simply look for arr[i] – 1 in hash, if not found, then this is the first element a subsequence. If this element is a first element, then count number of elements in the consecutive starting with this element. If count is more than current res, then update res.
- *** Find the two repeating elements in a given array – Given an array of integers where each value 1 <= x <= len(array), write a function that finds all the duplicates in the array. GFG.
1. Brute Force – Time Complexity: O(n*n) Auxiliary Space: O(1)
2. Use Count array – Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate.
Time Complexity: O(n) Auxiliary Space: O(n)
3. Make two equations – Let the numbers which are being repeated are X and Y. We make two equations for X and Y. We know the sum of integers from 1 to n is n(n+1)/2 and product is n!.
We calculate the sum of input array, when this sum is subtracted from n(n+1)/2, we get X + Y because X and Y are the two numbers missing from set [1..n]. Similarly calculate product of input array, when this product is divided from n!, we get X*Y. Given sum and product of X and Y, we can find easily out X and Y. This approach is a bit constrained in the sense that all the no. be should be present in the given range. But the logic can be useful in some other question.Let summation of all numbers in array be S and product be P
X + Y = S – n(n+1)/2
XY = P/n!
4. Use array elements as index: Works only for positive no and number within the range. Java method for absolute value – Math.abs();
Variation 1: What if the array is too large to put in memory? use external merge sort.
Variation 2: What if the array is too large to store on one machine and we have to distribute it to multiple nodes?
5. Use XOR (SO)
- Find duplicates in array. Link. This is a variation to handle when the data is too big to fit in memory.
- *** Find the two non-repeating elements in an array of repeating elements OR Find the two numbers with odd occurrences in an unsorted array – GFG SO
Algo:
***1. Use XOR A O(n) time and O(1) extra space solution. Code
All numbers except two are repeated. If we do a XOR of all array elements we finally get a XOR of the two non repeated number, say x and y. We find the rightmost set bit in this final xor using the formula,
set_bit_no = xor & ~(xor-1)
So if we take any set bit(in the above case we are taking rightmost) of xor and divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. Now if we XOR all elements from which have set_bit_no set, then all the same elements will be XOR’ed twice except the repeated one and we will find the number.
The rightmost set bit is very important. If we do a &(bitwise and) with a number which has same bit position set then we will get the same number as set_bit_no else we get a 0 every-time, as it’s a and operation(check the code). Based on that we create two set of numbers.
Note: Do not confuse the above formula with Brian Kernighan’s Algorithm., used to count set bits in an integer, which is
n & (n-1).
2. Sorting
3. Hashing table
4. Brute Force
Similar: You are given a read only array of n integers from 1 to n. Each integer appears exactly once except A which appears twice and B which is missing. Return A and B.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Asked in Amazon.
Algo: XOR all element from 1 to n with the array given. This will leave us with XOR of missing number and the number that’s repeated twice. This is a known problem.
1. use the XOR logic
2. Sort but that’s not O(n) time complexity
3. Hashing but that’s not O(1) space complexity
Similar: Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. GFG
- *** Find duplicates in O(n) time and O(1) extra space GFG
Using Brute force or hash or sorting is on obvious solution here but that won’t satisfy the constraint given here.
Algo:
1. Use array elements as index. Find the two repeating elements in a given array (question 2 on this page) also uses this approach.
2. **Use the array value as index. Approach 2. The question below uses the same approach. We use the array value as array index(since the numbers are in range 1 to n).
- *** Count frequencies of all elements in array in O(1) extra space and O(n) time. GFG
Approach 1: Skip
Approach 2: The basic idea is to use array value as array index. We take the array value, modulo that with the n (n = max no. of elements, array values given are in range 1 to n). Now if we do this, how do we avoid the case of losing the original value at that index.
We use the array value as array index. This work because all number are in range 1 to n. So we take the modulo of the element with the max n given. This will give a number in the range of array. This basically is the array index corresponding to the array value. We add n to that position. We keep doing this for all the element. If a element is repeated 3 times, then it’s index value would have increased by 3*n times. If we divide this value by n, we get 3 which is basically the frequency.
See the code for rest of the explanation.
Code
*** Similar: Find the maximum repeating number in O(n) time and O(1) extra space.
Uses approach 2.
*** Similar: Given an of array of n + 1 integers between 1 and n, find one number that repeats in linear time using less than O(n) space and traversing the stream sequentially O(1) times. Question. Asked in Amazon.
- Given a sorted array and a value x. The floor of x is the largest element in array smaller than or equal to x. GFS. Algo:
1. the first approach is O(n) time. Linearly traverse the array and ….
2. O(logn). Yes we can do better then O(n). Do a binary search
- Find the Missing Number – You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. GFG
Algo:
1. Sum method. Find the two repeating elements in a given array also uses this approach. This is same as first problem on this page.
2. *** XOR approach
3. Sort
- *** 2 Sum Problem – Given an array A and a number x, check for pair in A with sum as x. GFG. Two approach
1. Use Sorting with double pointers. This double pointer concept comes handy other problem as well.
2. Using hashing. Check if the sum – a[i] exists in the table. If yes, then found else add a[i] hash table.
– *** Variation 1 : An Array of integers is given, both positive and negative. Find 2 integers in an array whose sum is closest to 0.GFG
Algorithm:
1) Sort all the elements of the input array.
2) Use two index variables l and r to traverse from left and right ends respectively and update the pointers accordingly.
3) How to decide whether to move the pointer towards left or right ? The question specifies, closed to 0. So we use this fact and move. So if sum is less than 0, move the left pointer else right.
– *** Variation 2: Find pair of numbers whose sum is 0 and each number can be repeated multiple times to generate this sum. Code. We can remove the duplicate and proceed.
Variation 3: Pythagorean Triplet in an array – Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a2 + b2 = c2. GFG.
Find square of every element and store as a sorted array. Now solve it like a 2 sum problem. Fix one element(obviously) the last one and then find pairs that add upto it. O(n^2)
- 3 Sum Problem : *** Sum of three nos. in an array that adds to a given number. For this problem the approach is based on the problem – sum of two nos. in an array adds to a given no. Link GFG
Algo –
1. Brute Force
2. As 2sum solution, let’s sort the array first. Now if we fix one number X in the array, the problem becomes finding 2 numbers that sum up to -X, which is exactly the 2sum question and can be solved in O(N) time.Therefore, we can iterate over each number and inside the loop, solve the sub-problem as 2sum. To calculate the time complexity, sorting is O(NlogN), the outside loop is O(N) and the inside 2sum is O(N). Therefore, the overall time complexity is O(N^2) and space complexity is O(1).
Note: So the best time complexity achieved is O(N^2).
– Variation 1 : An Array of integers is given, both positive and negative. Find 3 integers in an array whose sum is closest to 0. Link GFG- Sort the array.
- Iterate over the array by fixing one integer X at a time.
- Find the 2 integers from the rest numbers whose sum is closest to -X.
- At the end of the iteration, we can output the result.
– Variation 2 : Find pair of numbers whose sum is 0 and each number can be repeated multiple times to generate this sum. Check This. Can’t we just remove the duplicate and handle this case ?
- *** 4 Sum – Given an array of integers, find all combination of four elements in the array whose sum is equal to a given value X. GFG
Algo 1: Time complexity: O(n^3).
1) Sort the input array.
2) Fix the first element as A[i] where i is from 0 to n–3. After fixing the first element of quadruple, fix the second element as A[j] where j varies from i+1 to n-2. Find remaining two elements in O(n) time, using the method 1 of this post. The inner loop is like a 2 sum problem. Keep notice of the index value, to avoid index out of bound error.
Algo 2: Code Time complexity: O(n^2). The idea is to consider every pair of elements in the array one by one and insert it into a map. For each pair of element (i, j), we calculate the remaining sum. If remaining sum exists in the map and elements involved in previous occurrence don’t overlap with the current pair i.e. ((i, j, i, y) or (i, j, x, i) or (i, j, j, y) or (i, j, x, j)), we print the Quadruplet and return. We also need to store the index of loop in the map. No sorting required.
- Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n. GFG.
Algo 1: Brute Force
Algo 2: Hashing
Algo 3: Sorting and Binary Search.We can use sorting and Binary Search to improve time complexity to O(nLogn). The first step is to sort the array in ascending order. Once the array is sorted, traverse the array from left to right, and for each element arr[i], binary search for arr[i] + n in arr[i+1..n-1]. If the element is found, return the pair. Both first and second steps take O(nLogn). So overall complexity is O(nLogn).
Can’t be solved using double pointers.
- *** Remove duplicate from an Array – Code – CareerCup GFG– So this is daunting because if we remove one element from an array we need to shift rest of the element. This is basically a conceptual part here and so we can’t simply do a unset here. So we will create a new array, so here now the main task will be to identify the duplicate.
General Approach – Use set(hset) to keep track of the element already present in the new array. We loop through the array and check if the current element exists in the hset, if not add it to the new array and hset and move ahead….
Hset will use space a lot of space. So what we can do it to use a bloom filter here or an bit array to keep track of the elements added. This save a lot of space.
** Sorting – Code we maintain two pointers i = 1 and j = 0. If both are different then we have encountered a new new element, we copy the element at i to element at j and move i and j to next position. If both are same then we move only i.
What we are basically trying to do is to maintain j at the first occurence of a element, so that when a new element is encountered we can copy that to the next position of j( at j +1). i is kept moving forward in search if new element and as it is found is copies that element to the next position of repeated element( which is j).
Similar: Given an array of primes such that the range of primes is small. Remove duplicates from the array. Since the range is small we can use set or sorting.
Asked in Amazon.
- Given two sorted arrays, find their union and intersection. GFG.
Algo:
1. Traverse both the array simultaneously. Rest if simple.
Complexity = O(2n) ~ O(n) Code
2. Store the element of one array in hash table and then start looping through the other array. Rest is simple. complexity – O(n) and space complexity O(n)
3. Since the array is sorted we can do a binary search. complexity – O(nlogn)
- You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Find the missing number. GFG .
Algo –
1. Use the sum of all the number in the array. we know the formula for sum on first n natural number, calculate that. find the difference and that’s the missing number.
2. Use XOR. XOR all the given number and number from 1 to n. Code
Variation 1: Given an array of n unique integers where each element in the array is in range [1, n]. The array has all distinct elements and size of array is (n-2). Hence Two numbers from the range are missing from this array. Find the two missing numbers. GFS
1. ** Use XOR. This is same as question 4 on this page(GFG) (Code).
2. Use sum and product formula to get the general equation to solve. Sum formula we already know. Product of first n number is n!. We get two equation solve with two variable. This forms a quadratic. This can result in overflow error
3. Use the average logic here. Same as the above approach. See the explanation on GFS.
- *** Given an sorted array of positive integers, count number of occurrences for each element in the array. Assume all elements in the array are less than some constant M. Do this without traversing the complete array. i.e. expected time complexity is less than O(n). GFS. Code
Algo: Modified Binary Search
- Find smallest and second smallest element in an array. GFS. We generally won’t think of traversing the array twice.
1. Sort the array. O(nlogn)
2. Traverse the array once and find the largest and second largest. O(n)
- *** [Pending] Rotate square matrix by 90 degrees OR Rotate an image by 90 degrees – Microsoft
1. inplace
2. using extra space
- We are given an array (or string), the task is to reverse the array. Code
- *** Find Majority Element in an Array. Boyer–Moore majority vote algorithm Youtube Code / Code OR
You’re given a read only array of n integers. Find out if any integer occurs more than n/3 times in the array in linear time and constant additional space.
** 1. Moore Algorithm. We maintain a counter for checking the maximum occurring element. Since an element occurs maximum number of times if we maintain a count for element and increment the count when we see the majority and decrement when we see any other value, then our count will be positive.
So when we start the algo we assume that i = 0 is max element index and set counter = 1. When we get the same element as the majority index element we increment the counter and if it’s different we decrement the counter. When the counter reaches 0, we reset the counter = 1 and take the current index as maximum index.
The second part of the algo involves verifying that the majority element calculate is in fact majority.
2. HashMap
3. Binary Search Tree
4. Brute Force
- Count number of occurrences (or frequency) in a sorted array. GFG
Algo: find the first and last occurrence of the given number using binary search.
Time complexity is O(Logn).
- ** Element that is repeated first – Oracle. GFG
1. Brute force
2. Sorted with binary search – Copy the main input to a temp array and sort this array. Start traversing the main array and for each element do a binary search on the sorted temp array. The first element that has a count more then 1 is the first repeated element.
3. Hashing – The idea is to traverse the given array from right to left and update the minimum index whenever we find an element that has been visited on right side. Code.
When we move from right to left. If an element is not present in set we add it to set else if it’s already added we know that it’s repeated and so till this point while traversing backward this would be the element that was repeated first.
(Do not confuse this with Boyer-Moore Vote Algorithm in the Majority Element in an Array question – that is for majority and not frequency).
- *** Next Greater Element for every given element in an array. GFS
Algo: This is similar to the question where we need to find the smaller element to the left. Use Stack. Similar : GFG
Similar: Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side. GFG
- *** Find an element in a sorted and rotated array. Check Code on GFG. O(log(n))
Algo – Binary Search. This is very similar to the previous problem.
– We can find the pivot. Then our array is divided into two parts – see in which part the number searched to be lies and do a binary search in that part.
– Without finding pivot1) Find middle point mid = (l + h)/2 2) If key is present at middle point, return mid. 3) Else If arr[l..mid] is sorted a) If key to be searched lies in range from arr[l] to arr[mid], recur for arr[l..mid]. b) Else recur for arr[mid+1..r] 4) Else (arr[mid+1..r] must be sorted) a) If key to be searched lies in range from arr[mid+1] to arr[r], recur for arr[mid+1..r]. b) Else recur for arr[l..mid]
- *** Find a pair with a given sum in sorted and rotated array – GFG – Given an array that is sorted and then rotated around an unknown point. Find if array has a pair with given sum ‘x’. It may be assumed that all elements in array are distinct.
Code Algo:
Approach 1: Since it’s a sum pair we can use hash. But that has O(n) time and O(n) space complexity.
Approach 2: If we find the pivot, we get the max and min element. Now we can reduce it to a problem – find the pair which adds upto a sum in a sorted array. We can have two pointers – at min and max index.
Now the logic to increment and decrement needs to be changed – we will be using modulo here – since we want complete array to be traversed. If we don’t do that then we end our calculation at the array length(min pointer) and 0 (max pointer).
We set the max pointer before pivot and min at pivot. Then we need to check for the pair. Since the left pointer can roll over to the starting of the array we are covering the entire array.
Time complexity of the above solution is O(n). The step to find the pivot can be optimized to O(Logn) using the Binary Search approach.
- Given a sorted array of n distinct integers rotated at some point. Given a value x. The problem is to count all the elements in the array which are less than or equal to x. GFG.
Algo – Find the pivot. This will split the array into two half. Search in the half in which x lies (simply compare the start and end, as both part of array will be sorted). Then count the number of element less then x, simply use binary search to get index of element greater that x.
Dependent: Find the position where a given element should be inserted in a sorted array. Code
- *** Print in Order -> LeetCode. Related to java Concurrency. Solution
- Search an element in an array where difference between adjacent elements is 1. GFG
Algo:
The idea is to start comparing from the leftmost element and find the difference between current array element and x. Let this difference be ‘diff’. From the given property of array, we always know that x must be at-least ‘diff’ away, so instead of searching one by one, we jump ‘diff’.
- *** Find the smallest positive integer value that cannot be represented as sum of any subset of a given array. GFG. Code. Explain.
- *** K-th Largest Sum Contiguous Subarray. Given an array of integers, find the K-th largest sum of contiguous subarray within the array of numbers which has negative and positive numbers. GFG
Lets Code 