Array Set 3

Array Set 1 
Array Set 2
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. 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, 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.
    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.
    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.
    if x is less then low, then a[0] is ceil. if x is less then high, then ceil does not exists.
    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: We use a stack here.
    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.


  10.  Given an unsorted 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: It’s like finding the ceil and floor in a sorted array using binary search.


  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: 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 generalized 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. Then XOR this set and the original given set.
Advertisements

One thought on “Array Set 3

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s