Array Set 3

Array Set 1 
Array Set 2

  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
    We basically maintain an array 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. Then we keep adding element and increasing it’s 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 that 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.
    1. Brute force
    2. Sorting
    3. Hashing
    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.

  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.
    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. We should always check if given x lies within the array ie. a[low] x < a[high ], if not then we can exit with proper output.
    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. Algo: O(n)

     1) Initialize both first and second smallest as INT_MAX
       first = second = INT_MAX
    2) Loop through all the elements.
       a) If the current element is smaller than first, then update first 
           and second. 
       b) Else if the current element is smaller than second then update 

  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. Just need to move one array index at a time to keep things simple and if clean.

  8. Given an array with both +ive and -ive integers, return a pair with highest product. Time complexity: O(n).  Read complete question and example on GFG.
    The max product will be either max two positive number or max two negative number.
    1. So we can either sort the array and get these values.
    2. We can traverse the array and keep track of these 4 values. O(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.
    1. 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.
    4. 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.  O(n) time O(1) extra space. GFG.
    : Have a pointer at the starting of one array and one at the end of other array. Then move the pointer accordingly.

  12. Queries for greater than and not less than
    Straightforward expected solution.

  13. Given an array of distinct elements, find third largest element in it.
    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. ** Move all zeroes to end of array 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.
    1. Maintain two pointers one at start and one at end. For every zero that start points to we move it to the end of array. This method will change the relative order of the numbers.
    2. Check code on GFG. Code.

  16. Sum of absolute differences of all pairs in a given array. GFG
    note you add each number exactly k times (where k is its place if you sort the list)
    also, you subtract each number exactly n-1-k times
    you can sort the list (O(nlogn)) and then iterate over the sorted array, multiplying each element as mentioned above.
    For example: Given a[]= {2,3, 5, 7 };
    output would be (3-2) + (5-2) + (7-2) + (5-3) + (7-3) + (7-5) = 17.
    –  Sum the multiplication of each number starting backwards with #count – 1 to get the total.
    – Sum the multiplication of each number starting up front with #count – 1 to get the total to subtract
    This would then become (7*3 + 5*2 +3*1) – (2*3 + 3*2 + 5*1) = 17

Leave a Reply

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

You are commenting using your 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