Solutions for Index Difference

    • @GarretVam
    • @mason, submitted in Python 2, achived 100% score
    def solve(v):
        n = len(v);
        maxFromEnd = [-38749432] * (n + 1);
    
        # Create an array maxfromEnd
        for i in range(n - 1, 0, -1):
            maxFromEnd[i] = max(maxFromEnd[i + 1], 
                                v[i]);
    
        result = 0;
    
        for i in range(0, n):
            low = i + 1; high = n - 1; ans = i;
    
            while (low <= high):
                mid = int((low + high) / 2);
    
                if (v[i] <= maxFromEnd[mid]):
    
                    # We store this as current
                    # answer and look for further
                    # larger number to the right side
                    ans = max(ans, mid);
                    low = mid + 1;
                else:
                    high = mid - 1;        
    
            # Keeping a track of the
            # maximum difference in indices
            result = max(result, ans - i);
    
        return result
    
    
    • @GarretVam
    • @mason, submitted in Python 3, achived 100% score
    def solve(v):
        n = len(v);
        maxFromEnd = [-38749432] * (n + 1);
    
        # Create an array maxfromEnd
        for i in range(n - 1, 0, -1):
            maxFromEnd[i] = max(maxFromEnd[i + 1], 
                                v[i]);
    
        result = 0;
    
        for i in range(0, n):
            low = i + 1; high = n - 1; ans = i;
    
            while (low <= high):
                mid = int((low + high) / 2);
    
                if (v[i] <= maxFromEnd[mid]):
    
                    # We store this as current
                    # answer and look for further
                    # larger number to the right side
                    ans = max(ans, mid);
                    low = mid + 1;
                else:
                    high = mid - 1;        
    
            # Keeping a track of the
            # maximum difference in indices
            result = max(result, ans - i);
    
        return result