Given an array arr[], find the maximum j – i such that arr[j] > arr[i] in c#

General
1

To solve the problem of finding the maximum ( j - i ) such that ( \text{arr}[j] > \text{arr}[i] ) for a given array, you can use a two-pointer technique after preprocessing the array to create two auxiliary arrays. This approach will help you achieve an efficient solution.

Algorithm Explanation

  1. Preprocessing: Create two auxiliary arrays:

    • leftMin: This will store the minimum value from the start of the array up to each index.
    • rightMax: This will store the maximum value from each index to the end of the array.

  2. Two-Pointer Technique: Use two pointers to iterate through the leftMin and rightMax arrays:

    • Start both pointers at the beginning of their respective arrays.
    • If ( \text{rightMax}[j] > \text{leftMin}[i] ), calculate ( j - i ) and update the maximum distance if it’s larger than the previous maximum. Then, move the j pointer forward.
    • If ( \text{rightMax}[j] \leq \text{leftMin}[i] ), move the i pointer forward to find a larger minimum value.

  3. Return the Result: The maximum distance found will be the answer.

C# Implementation

Here’s how you can implement this in C#:

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 34, 8, 10, 3, 2, 80, 70, 60, 50 };
        int maxDistance = MaxIndexDifference(arr);
        Console.WriteLine("Maximum j - i such that arr[j] > arr[i]: " + maxDistance);
    }

    static int MaxIndexDifference(int[] arr)
    {
        int n = arr.Length;

        // Step 1: Create the leftMin and rightMax arrays
        int[] leftMin = new int[n];
        int[] rightMax = new int[n];

        leftMin[0] = arr[0];
        for (int i = 1; i < n; i++)
        {
            leftMin[i] = Math.Min(leftMin[i - 1], arr[i]);
        }

        rightMax[n - 1] = arr[n - 1];
        for (int j = n - 2; j >= 0; j--)
        {
            rightMax[j] = Math.Max(rightMax[j + 1], arr[j]);
        }

        // Step 2: Use two pointers to find the maximum j - i
        int maxDiff = -1;
        int i = 0, j = 0;

        while (i < n && j < n)
        {
            if (rightMax[j] > leftMin[i])
            {
                maxDiff = Math.Max(maxDiff, j - i);
                j++; // Move j forward to find a larger j
            }
            else
            {
                i++; // Move i forward to find a larger leftMin
            }
        }

        return maxDiff;
    }
}

Explanation of Code

  1. Input: The program defines an array arr with some integer values.
  2. MaxIndexDifference Function:
    • Initialization: It first creates two arrays, leftMin and rightMax, both of size n.
    • Populating leftMin: The first loop populates leftMin such that each index contains the minimum value from the start of the array up to that index.
    • Populating rightMax: The second loop populates rightMax such that each index contains the maximum value from that index to the end of the array.
  3. Finding Maximum Distance:
    • Using two pointers (i and j), the function iterates through the leftMin and rightMax arrays.
    • If rightMax[j] > leftMin[i], it calculates the difference ( j - i ) and updates maxDiff if it’s greater than the current maximum. It then increments j.
    • If rightMax[j] <= leftMin[i], it increments i to check the next minimum value.
  4. Return the Result: Finally, the function returns the maximum difference found.

Complexity

  • Time Complexity: O(n), where n is the length of the array. The algorithm traverses the array a constant number of times.
  • Space Complexity: O(n), due to the storage of the leftMin and rightMax arrays.

This approach efficiently computes the desired maximum difference while maintaining clarity and performance.