Max Distance Asked in: Google Amazon Microsoft

 Problem Description

Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].



Input Format

First and only argument is an integer array A.



Output Format

Return an integer denoting the maximum value of j - i;



Example Input

Input 1:

 A = [3, 5, 4, 2]


Example Output

Output 1:

 2


Example Explanation

Explanation 1:

 Maximum value occurs for pair (3, 4).


Solution:

class Solution:
    # @param A : tuple of integers
    # @return an integer
    def maximumGap(self, A):
        n=len(A)    
        R = [0] * n     
        R[n - 1] = A[n - 1] 
        for j in range(n - 2, -1, -1): 
            R[j] = max(A[j], R[j + 1]); 
    
        i = 0;j=0
        diff = -1
        while (j < n and i < n): 
            if (A[i] <= R[j]): 
                diff = max(diff, j - i) 
                j+=1
            else: 
                i+=1
    
        return diff
            
      
           

Screenshot:




Comments

Popular posts from this blog

Trouble with the Number System

Residue Arithmetic

Perfect Peak of Array