The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Arrays & Strings

Problem :-
Given an array of 'n' elements, find max( j - i ) s.t arr(j) > arr(i).
Consider the array { 7, 2, 6, 3, 5, 1 } .
Max( j - i ) = 3 where j = 4 & i = 1 and arr(4) > arr(1).

Solution :-
We need to maintain two temporary arrays min_from_left (Value at each index is the min value found till that index starting from left) & max_from_right (Value at each index is max value found till that index starting from right). Let max_diff holds max ( j - i ). Iterate over the two temporary arrays and update max_diff.
See the implementation below.

#include<iostream>
using namespace std;

int max(int x, int y) {
   return ((x > y) ? x : y);
}

int min(int x, int y) {
   return ((x < y) ? x : y);
}

// find max (j-i) s.t arr[j] > arr[i]
int findMaxDiffIndex(int arr[],int size) {
   int max_diff;
   // array in which each index holds the minimum element found 
   // so far starting from left  
   // i.e arr[i] = min(arr[0...i]);
   int min_from_left[size];
   // array in which each index holds the maximum element found 
   // so far starting from right 
   // i.e arr[j] = max(arr[j...size-1]);
   int max_from_right[size];
   int i,j;
   min_from_left[0] = arr[0];
   for (i=1;i<size;i++) {
      min_from_left[i] = min(min_from_left[i-1],arr[i]);
   }
   max_from_right[size-1] = arr[size-1];
   for (j=size-2;j>=0;j--) {
      max_from_right[j] = max(max_from_right[j+1],arr[j]);
   }
   i = 0;
   j = 0;
   max_diff = -1;
   // iterate over the two temporary arrays
   while (i < size && j < size) {
      if (min_from_left[i] < max_from_right[j]) {
         // update the max diff
         max_diff = max(max_diff,j-i);
         j++;
      }
      else {
         i++;
      }
   }
   return max_diff;
}

// main
int main() {
   int arr[] = {29,11,7,19,62,24,1,5};
   int size = sizeof(arr)/sizeof(arr[0]);
   int max_diff = findMaxDiffIndex(arr,size);
   cout<<"\nMax Index Difference :: "<<max_diff;
   cout<<endl;
   return 0;
}

Back | Next

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j - i ) s.t arr(j) > arr(i)