# Array Set 3

Array Set 1
Array Set 2
1, 2, 4, 5, 14, 15, *17, *18, *19, *20, *21, 23, 24, 25, 26, 27, 28
Basics – Hash, Sort, XOR, Array element as index, Simple traversal

1. *** Given an array of of size n and a number k, find all elements that appear more than n/k times. GFG. Code. Brief
Algo:
1. Sort the array and count
2. Store in HashMap with count and then print.
3. We basically maintain an array of size (k-1) which has keeps track of element and it’s frequency(n/k maximum value will be k-1). But we don’t maintain the count of all the element. We know that the will be k-1, so we keep the array size as k-1. Start traversing and keep adding element and increasing its count. When the array is full, we remove element from it. But how to do that. So we decrement the count of every element by one(but don’t remove that element, we will skip adding that element). Then if a new element comes we will check in that array if any element has count 0, if yes we will replace it. Else if already exists we will increment that count. If an element has been repeated n/k times, it will get back to the this array eventually. (It’s something like the majority array count).

2. ** You are given an unsorted array with both positive and negative elements. You have to find the smallest positive number missing from the array in O(n) time using constant extra space. You can modify the original array. GFG
Algo:
1. Brute force O(n^2)
2. Sorting. O(nLogn + n) time which is O(nLogn)
3. Hashing. O(n) time on average, but it requires O(n) extra space.
4. Use array element as index. The solution on GFS remove all the negative element in the array. Then for the positive array(>=1), it uses array element as index. For each element i, abs(a[i]) – 1 (0 indexed array), then set this value in the array as negative. Repeat this for every element in the array.
O(n) time and O(1) extra space.

3. ** An Array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero. GFS.
Algo: O(nlogn) + O(n) ~ O(nlogn)
Sort the array and take pointers at the start and the end. Keep moving these accordingly. Keep track of the minimum sum and the elements corresponding to these sum. How do we move the pointers, the questions say ‘closet to zero’. that’s the key.
This is a 2 sum problem variation.

4. ** Given an unsorted array of size n. Array elements are in range from 1 to n. One number is missing and one number occurs twice in array. Find these two numbers. Asked in Google, Amazon. GFG
Algo:
1. Sorting, Time Complexity: O(nLogn)
**2. Use XOR,Time Complexity: O(n)
**3. Use Array element as index – We traverse the array and set array index corresponding to the array value.  We use the abs value of the array value and mark index, value-1 (since 0 index) as -value (set negative value, this helps us identify that the index has been visited). Before setting the index value we check if it’s value is negative. If yes then that node has already been visited(why ? bcoz it’s value has been negative by some other index).
The element whose node index value is still positive means has not been set. So that index + 1, value is missing in the array.

5. ** Ceiling in a sorted array – Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order.  GFS
Algo: Use Binary Search.
Do not confuse this with local minima or peak in an array problem(Q5 array set 2).

6.  Find the smallest and second smallest elements in an array. GFG
Algo:
1. In a single traversal find the smallest and second smallest. O(n)
2. Sort the data.  O(n Log n)

7. Given three arrays sorted in non-decreasing order, print all common elements in these arrays. GFG.
Algo:
1. Same as intersection of two array. Here we will have to use 3 pointers instead. Start the loop. At each index, check which pointer needs to be moved. First check if all are same. Else keep checking each array index value and move accordingly. We will be moving just a single index at a time (why ? consider if i < j = k. if we change two pointers we will be missing an intersection).
Complexity – O(l+m+n)

8. Given an array with both +ive and -ive integers, return a pair with highest product.  GFGAlgo:
Sort the array. The max product will be either max two positive number or max two negative number.
Time complexity: O(n(log(n)))

9. *** Given an array of integers, find the nearest smaller number for every element such that the smaller element is on left side. GFG
Algo: Stack
If the stack is not empty and the top of stack > current element, pop all element.
Do this till either stack is empty or top of stack is smaller then current element.
–  If stack is empty it means that current element has no smaller element. Print it.
–   If non empty then top is smaller. Print it.
Push the current element onto stack.
Wrong: https://ideone.com/nKAcvp. Just keeping track of the last smallest won’t work. Consider the case, 1 2 3 5 4. To decide the smallest when going back we use the stack.
Check this also

10.  Given an unsorted array of distinct integers, find the largest pair sum in it. For example, the largest pair sum in {12, 34, 10, 6, 40} is 74.  GFG
Expected Time Complexity: O(n) [Only one traversal of array is allowed]
Algo: Just find the largest and second largest element of the array in one traversal.

11. Given two sorted arrays and a number x, find the pair whose sum is closest to x and the pair has an element from each array.  GFG.
Algo
: Have a pointer at the starting of one array and one at the end of other array. Then move the pointer accordingly. O(n) time O(1) extra space

12. Queries for greater than and not less than
Algo: Since we need to answer a lot of queries for the same dataset, we will sort the array and use binary search. This will take O(NlogN + QlogN).

13. Given an array of distinct elements, find third largest element in it. GFG
Algo: Try to solve this in only one traversal of array. Just keep three variable –  first, second and third. Keep updating these accordingly.
Similar Logic: Find the largest three elements in an array

14. ** Given an array where difference between adjacent elements is 1, write an algorithm to search for an element in the array and return the position of the element (return the first occurrence). GFG
Algo: Start traversing the array. We use the fact given in question to jump more than 1 step at a time. 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’.

15. ** Given an array of random numbers, Push all the zero’s of a given array to the end of the array. For example, if the given arrays is {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0}, it should be changed to {1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0}. The order of all other elements should be same. Expected time complexity is O(n) and extra space is O(1). GFG. Asked in Amazon.
Algo: The idea is to first move all the non-zero number to the start and then fill the rest of the array with zero.
We keep a counter say c = 0. We start traversing the array. For for non-zero element encountered we push that to the index c and we increment c. This will basically start copying element form non-zero index to the starting of the array. When the loop breaks all non-zero are in the starting. Now for the rest of the array, c to n, set everything as 0.

16. ** Sum of absolute differences of all pairs in a given array. GFG
Algo: An efficient solution for this problem needs a simple observation. Since array is sorted and elements are distinct, when we take sum of absolute difference of pairs each element in the i’th position is added ‘i’ times and subtracted ‘n-1-i’ times.
For example in {1,2,3,4} element at index 2 is arr[2] = 3 so all pairs having 3 as one element will be (1,3), (2,3) and (3,4), now when we take summation of absolute difference of pairs, then for all pairs in which 3 is present as one element summation will be = (3-1)+(3-2)+(4-3). We can see that 3 is added i = 2 times and subtracted n-1-i = (4-1-2) = 1 times.
The generalised expression for each element will be
sum = sum + (i*a[i]) – (n-1-i)*a[i]

17. *** Given an integer array, one element occurs even number of times and all others have odd occurrences. Find the element with even occurrences. Link
Algo:  Get all the unique number from the given set – so all element has odd occurence.  Then xor it with the original array – so all even times element will be xor’ed odd times and odd elements will be xor’ed even times. Thus only the even times repeated element will be left in the end.

18. *** 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

19. ***** Link Maximum j-i Such That arr [j] > arr [I] . GFG

20. ***** Maximum difference between two elements such that larger element appears after the smaller number. GFG Solve like the above problem. Code

21. ***** Find if two rectangles overlap. GFG
Note : It may be assumed that the rectangles are parallel to the coordinate axis.
Algo: Two rectangles do NOT overlap if one of the following conditions is true.
1) One rectangle is above top edge of other rectangle.
2) One rectangle is on left side of left edge of other rectangle.
These both condition will have to be verified for both set of rectangles given.

22. *** How to check if two given line segments intersect.  GFG
Algo:

23. **** Find the minimum distance between two numbers. GFG There will be duplicates. Code
Algo: GFG solution is complicated. follow the above code.
Save the index of x or y whichever is found. Calculate the min diff b/w these if they have been found at-least once (If only 1 has been found u can’t calculate the min diff).  Keep updating the min distance whenever in each traversal.

24. *** Shuffle a given array. GFG –
Fisher–Yates shuffle Algorithm works in O(n) time complexity.

```To shuffle an array a of n elements (indices 0..n-1):
for i from n - 1 downto 1 do
j = random integer with 0 <= j <= i
exchange a[j] and a[i]```

25. *** Generate all subarray for a given array. GFG
Algo: Complexity(n^3)
In general, for an array/string of size n, there are n*(n+1)/2 non-empty subarrays/substring.

26. *** Subsets of a given set. GFG / GFG.
The total number of subsets of any given set is equal to 2^ (no. of elements in the set).  The total number of subsets of any given set is equal to 2^ (no. of elements in the set) and all are in the range 0 to (2^n -1). So we generate all the numbers from 0 to 2^n-1 and for each number check bit. If the bit is set we print the array element else not. BigInteger.valueOf(counter).testBit(j).
Time Complexity O(n * 2^n)
Check this also

27. *** Maximum sum such that no two elements are adjacent. TR-Video Code
Algo: We use two param – inc, exu. inc is the maximum sum till the index i if i was included. exu is the maximum sum till index i if i is not included. GFG
inc at index i does not means that i is included – it may or may not be.

28. *** Maximum sum of pairs with specific difference. GFG
Algo: Sort the array. Then start checking each pair from the end. To get maximum possible sum, iterate from largest to smallest, giving larger numbers priority over smaller numbers.
29. Find the minimum distance between two numbers. GFG
30. **** Min-Max Range Queries in Array. GFG Segment Tree