Optimal path

 

You said:

(Given two arrays A, B with N elements, find the max. element in the optimal path from top left to bottom right. 3 4 6 :A[] 5 1 4 :B[] 3->4->1->4 is the optimal path and max value is 4 in optimal path.)

ChatGPT said:

This is a min–max path problem on a 2 × N grid.

Problem interpretation

• You are given two arrays A and B, each of size N.

• Think of them as a grid with:

  • Top row = A

  • Bottom row = B

• You start at top-left (A[0]) and must reach bottom-right (B[N-1]).

• Allowed moves:

  • Move right

  • Move down (only once, from A to B)

• The cost of a path is the maximum value on that path.

• Goal: choose a path that minimizes this maximum value, then report that value.

---

Example

A = [3, 4, 6]
B = [5, 1, 4]

Possible paths (down at column k):

1. Down at k = 0
   Path: 3 → 5 → 1 → 4
   Max = 5

2. Down at k = 1
   Path: 3 → 4 → 1 → 4
   Max = 4 ✅

3. Down at k = 2
   Path: 3 → 4 → 6 → 4
   Max = 6

Optimal path:
3 → 4 → 1 → 4
Answer: 4




Java Solution (O(N) time, O(N) space)

public class MinMaxPath {

    public static int minMaxPath(int[] A, int[] B) {
        int n = A.length;

        int[] prefixA = new int[n];
        int[] suffixB = new int[n];

        // Prefix max for A
        prefixA[0] = A[0];
        for (int i = 1; i < n; i++) {
            prefixA[i] = Math.max(prefixA[i - 1], A[i]);
        }

        // Suffix max for B
        suffixB[n - 1] = B[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixB[i] = Math.max(suffixB[i + 1], B[i]);
        }

        int answer = Integer.MAX_VALUE;

        // Try all possible columns to move down
        for (int k = 0; k < n; k++) {
            int pathMax = Math.max(prefixA[k], suffixB[k]);
            answer = Math.min(answer, pathMax);
        }

        return answer;
    }

    public static void main(String[] args) {
        int[] A = {3, 4, 6};
        int[] B = {5, 1, 4};

        System.out.println(minMaxPath(A, B)); // Output: 4
    }
}

---

Explanation with example

A = [3, 4, 6]
B = [5, 1, 4]

• Down at index 1

• Path: 3 → 4 → 1 → 4

• Max value = 4 ✅ (minimum possible)

---

Complexity

• Time: O(N)

• Space: O(N)
  (can be optimized to O(1) if needed)