Problem

Given three sorted arrays A, B and C of not necessarily same sizes.

Calculate the minimum absolute difference between the maximum and minimum number from the triplet a, b, c such that a, b, c belongs arrays A, B, C respectively. i.e. minimize | max(a,b,c) - min(a,b,c) |.

Examples

1
2
3
4
5
6
7
8
9

Input:
A : [ 1, 4, 5, 8, 10 ]
B : [ 6, 9, 15 ]
C : [ 2, 3, 6, 6 ]

Output:
1

Explanation: We get the minimum difference for a=5, b=6, c=6 as | max(a,b,c) - min(a,b,c) | = |6-5| = 1.

Solution

Method 1 - Use 3 pointers to track minimums

Here are the steps: The algorithm works by maintaining three pointers, initially set to the beginning of each array. At each step, it calculates the minimum and maximum values among the elements pointed to by these pointers. The goal is to minimize the difference between the maximum and minimum of the triplet.

  1. Initialize Variables: Set the initial difference to a large value.
  2. Iterate with Pointers: Use a while loop to iterate through all three arrays until one of them is exhausted.
  3. Calculate Min and Max: Find the minimum and maximum values among the current elements of the arrays.
  4. Update Minimum Difference: Update the smallest difference found so far.
  5. Move Pointer: Increment the pointer of the array that contains the minimum value.
  6. Break Condition: If the difference is zero, break the loop as it’s the smallest possible difference.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
    public int solve(int[] A, int[] B, int[] C) {
        // Initialize the result difference to a very large number
        int diff = Integer.MAX_VALUE;

        // Initialize min and max variables to track the current minimum and
        // maximum values among A[i], B[j], and C[k]
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;

        // Initialize pointers to iterate through arrays A, B, and C
        int i, j, k;

        // Iterate through all three arrays until one of them is exhausted
        for (i = 0, j = 0, k = 0;
             i < A.length && j < B.length && k < C.length;) {
            // Find the minimum and maximum values among A[i], B[j], and C[k]
            min = Math.min(A[i], Math.min(B[j], C[k]));
            max = Math.max(A[i], Math.max(B[j], C[k]));

            // Update the difference if the current difference is smaller
            diff = Math.min(diff, max - min);

            // If the difference is zero, break the loop since it's the smallest
            // possible difference
            if (diff == 0) {
                break;
            }

            // Move the pointer of the array that has the minimum value
            if (A[i] == min) {
                i++;
            } else if (B[j] == min) {
                j++;
            } else {
                k++;
            }
        }

        // Return the minimum difference found
        return diff;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        if not arr:
            return arr

        # Step 1: Sort the array while keeping track of the original indices
        sorted_arr = sorted(enumerate(arr), key=lambda x: x[1])

        # Step 2: Create a rank dictionary
        rank_dict = {}
        rank = 1

        for i, (index, value) in enumerate(sorted_arr):
            if value not in rank_dict:
                rank_dict[value] = rank
                rank += 1

        # Step 3: Replace elements in original array with their corresponding rank
        result = [rank_dict[arr[i]] for i in range(len(arr))]
        return result

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)