Maximum Difference Between Two Indices | Coding Interview | Sorting | 30 Days Preparation Plan | Day 2 — Problem 5

This problem is a medium category problem and has been asked by VMWare, Google, and Amazon.

For a better grasp of the problem, after reading each section, try to code that approach. If you get stuck 😉, you can always look at the commented code I have provided for your reference.

This problem is part of the 30 Days Preparation Plan.

Table of Contents

• Description
• Approach 1: Brute Force
• Code
• Time and Space Complexity
• Approach 2: Using Sorting
• Code
• Time and Space Complexity

Description

You are given an array of N integers. You have to determine the maximum difference between two indices i and j, such that i < j and Array[i] ≤ Array[j].

Let’s understand it using an example.

Example 1:
Input: [4, 2, 8, 9, 11, 4, 3, 1]
Output: 5
Explanation: Indices 1 and 6 satisfy the constraints as 1 < 6 and Array[1] < Array[6], (2 < 3).
Example 2:
Input: [4, 3, 2, 1]
Output…