1.3.1 Application

• Given an array A[] and a number x, check for pair in A[] with sum as x.
  1. Answer 1: Sort O(n*log(n))
     hasArrayTwoCandidates (A[], ar_size, sum) 
     1) Sort the array in non-decreasing order. 
     2) Initialize two index variables to find the candidate 
        elements in the sorted array. 
            (a) Initialize first to the leftmost index: l = 0 
            (b) Initialize second  the rightmost index:  r = ar_size-1 
     3) Loop while l < r. 
            (a) If (A[l] + A[r] == sum)  then return 1 
            (b) Else if( A[l] + A[r] <  sum )  then l++ 
            (c) Else r-- 
     4) No candidates in whole array - return 0

     Idea: Don’t need keep index information, so you can sort it.

  2. Answer 2: Hash O(n)
• Count triplets with sum smaller than a given value.
  1) Sort the input array in increasing order. 
  2) Initialize result as 0. 
  3) Run a loop from i = 0 to n-2.  An iteration of this loop finds all 
     triplets with arr[i] as first element. 
       a) Initialize other two elements as corner elements of subarray \newline 
          arr[i+1..n-1], i.e., j = i+1 and k = n-1 
       b) Move j and k toward each other until they meet, i.e., while (j < k)\newline 
              (i) if (arr[i] + arr[j] + arr[k] >= sum), then do k-- 
   
              // Else for current i and j, there can (k-j) possible third elements 
              // that satisfy the constraint.\newline 
              (ii) Else Do ans += (k - j) followed by j++

  Idea: Same Idea as previous question, Don’t need keep index information, so you can sort it.

• Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time and constant space. Example: I/P = [1, 2, 3, 2, 3, 1, 3] and O/P = 3.
  The Best Solution is to do bitwise XOR of all the elements. XOR of all elements gives us odd occurring element. Please note that XOR of two elements is 0 if both elements are same and XOR of a number x with 0 is x.

  Idea: Perform some calculation on all elements.

• 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. Write an efficient code to find the missing integer.
  1) Get the sum of numbers 
         total = n*(n+1)/2 
  2  Subtract all the numbers from total and you will get the missing number.

  Idea: Perform some calculation on all elements.

• Max product of the three numbers for a given array of size N.
  Find the three largest numbers in the array (n1, n2, n3) and the two smallest numbers (m1, m2). The answer is either n1 x n2 x n3 or n1 x m1 x m2

  Idea: Not sort, but nth max element based on heap

• Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number. Examples: Input: arr[] = 1, 4, 20, 3, 10, 5, sum = 33; Ouptut: Sum found between indexes 2 and 4
  Initialize a variable curr\_sum as first element. curr\_sum indicates the sum of current subarray. Start from the second element and add all elements one by one to the curr\_sum. If curr\_sum becomes equal to sum, then print the solution. If curr\_sum exceeds the sum, then remove trailing elemnents while curr\_sum is greater than sum.

  Idea: 1) You must keep index information, so you can’t sort. keep head and trail two index

• An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.
• Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller number in arr[]. Examples: If array is [2, 3, 10, 6, 4, 8, 1] then returned value should be 8 (Diff between 10 and 2). If array is [ 7, 9, 5, 6, 3, 2 ] then returned value should be 2 (Diff between 7 and 9)
  In this method, instead of taking difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things: 
  1) Maximum difference found so far (max\_diff). 
  2) Minimum number visited so far (min\_element).

  Keep position, but this problem can be divided by sub-problem. Such as, [ 7, 9, 5, 6, 3, 2 ] can be seen as [7,9] [5, 6] [3] [2] Once current element is less than min_element, begin a new sub-problem.

• Write a program to print all the LEADERS in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example int the array 16, 17, 4, 3, 5, 2, leaders are 17, 5 and 2.
  Scan all the elements from right to left in array and keep track of maximum till now. When maximum changes it’s value, print it.

  Same idea just like previous

• Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j. Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).
  1) Create an empty Set in C++ STL (Note that a Set in C++ STL is 
     implemented using Self-Balancing Binary Search Tree). And insert 
     first element of array into the set. 
   
  2) Initialize inversion count as 0. 
   
  3) Iterate from 1 to n-1 and do following for every element in arr[i] 
       a) Insert arr[i] into the set. 
       b) Find the first element greater than arr[i] in set 
          using upper_bound() defined Set STL. 
       c) Find distance of above found element from last element in set 
          and add this distance to inversion count. 
   
  4) Return inversion count.

  1) You need keep index(position) information. (No sort, no calculation). 2) you can’t divid it to subj-problem. 3) You have to use auxiliary DS outside. such as set. which store how many element is greeter than current element.

• Convert array into Zig-Zag fashion ? The converted array should be in form a < b > c < d > e < f.
  We can convert in O(n) time using an Efficient Approach. The idea is to use modified one pass of bubble sort. Maintain a flag for representing which order(i.e. < or >) currently we need. If the current two elements are not in that order then swap those elements otherwise not. 
  Let us see the main logic using three consecutive elements A, B, C. Suppose we are processing B and C currently and the current relation is ’<’. But we have B > C. Since current relation is ’<’ previous relation must be ’>’ i.e., A must be greater than B. So, the relation is A > B and B > C. We can deduce A > C. So if we swap B and C then the relation is A > C and C < B. Finally we get the desired order A C B
• Conclusion: Main methods for array questions.
  1. Clue1: Get max and min value, based on heap, init a heap need O(n), when you get the second largest or third largest one, you only need O(log(n)). It’s better than sort O(n*log(n) ).
  2. Clue2: Sort
  3. Clue3: For continuous subarray, keep head and trail two index.
  4. Clue4: Calculate, such as sum and bit operator XOR.
  5. Clue5: Use other auxiliary DS, such as, map, set or hash_map. They can be used as count and sort.