Problem

We have an integer array arr, where all the integers in arr are equal except for one integer which is larger than the rest of the integers. You will not be given direct access to the array, instead, you will have an API ArrayReader which have the following functions:

  • int compareSub(int l, int r, int x, int y): where 0 <= l, r, x, y < ArrayReader.length(), l <= r and x <= y. The function compares the sum of sub-array arr[l..r] with the sum of the sub-array arr[x..y] and returns:
    • 1 if arr[l]+arr[l+1]+...+arr[r] > arr[x]+arr[x+1]+...+arr[y].
    • 0 if arr[l]+arr[l+1]+...+arr[r] == arr[x]+arr[x+1]+...+arr[y].
    • -1 if arr[l]+arr[l+1]+...+arr[r] < arr[x]+arr[x+1]+...+arr[y].
  • int length(): Returns the size of the array.

You are allowed to call compareSub() 20 times at most. You can assume both functions work in O(1) time.

Return the index of the arrayarr which has the largest integer.

Examples

Example 1:

1
2
3
4
5
6
7
8

Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.

Example 2:

1
2

Input: nums = [6,6,12]
Output: 2

Constraints:

  • 2 <= arr.length <= 5 * 10^5
  • 1 <= arr[i] <= 100
  • All elements of arr are equal except for one element which is larger than all other elements.

Follow up:

  • What if there are two numbers in arr that are bigger than all other numbers?
  • What if there is one number that is bigger than other numbers and one number that is smaller than other numbers?

Solution

Method 1 – Binary Search with Interactive API

Intuition

Since all elements are equal except one which is larger, we can use binary search to find the unique large element. At each step, we compare the sum of the left and right halves using the compareSub API.

Approach

  1. Set left = 0, right = n - 1.
  2. While left < right:
    • Let len = right - left + 1.
    • If len is even, compare left half and right half.
    • If len is odd, ignore the middle element and compare the two equal halves.
    • Use compareSub to determine which half contains the large integer.
    • Narrow the search to the half with the larger sum.
  3. When left == right, return left as the index of the large integer.

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

/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * class ArrayReader {
 *   public:
 *     int compareSub(int l, int r, int x, int y);
 *     int length();
 * };
 */
class Solution {
public:
    int getIndex(ArrayReader &reader) {
        int n = reader.length();
        int l = 0, r = n - 1;
        while (l < r) {
            int len = r - l + 1;
            int mid = l + (r - l) / 2;
            if (len % 2 == 0) {
                int res = reader.compareSub(l, mid, mid+1, r);
                if (res == 1) r = mid;
                else l = mid + 1;
            } else {
                int res = reader.compareSub(l, mid-1, mid+1, r);
                if (res == 1) r = mid - 1;
                else if (res == -1) l = mid + 1;
                else return mid;
            }
        }
        return l;
    }
};
 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

// type ArrayReader interface {
//     CompareSub(l, r, x, y int) int
//     Length() int
// }
func getIndex(reader ArrayReader) int {
    n := reader.Length()
    l, r := 0, n-1
    for l < r {
        length := r - l + 1
        mid := l + (r-l)/2
        if length%2 == 0 {
            res := reader.CompareSub(l, mid, mid+1, r)
            if res == 1 {
                r = mid
            } else {
                l = mid + 1
            }
        } else {
            res := reader.CompareSub(l, mid-1, mid+1, r)
            if res == 1 {
                r = mid - 1
            } else if res == -1 {
                l = mid + 1
            } else {
                return mid
            }
        }
    }
    return l
}
 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

// This is the ArrayReader's API interface.
// You should not implement it, or speculate about its implementation
// interface ArrayReader {
//     public int compareSub(int l, int r, int x, int y);
//     public int length();
// }
class Solution {
    public int getIndex(ArrayReader reader) {
        int n = reader.length(), l = 0, r = n - 1;
        while (l < r) {
            int len = r - l + 1, mid = l + (r - l) / 2;
            if (len % 2 == 0) {
                int res = reader.compareSub(l, mid, mid+1, r);
                if (res == 1) r = mid;
                else l = mid + 1;
            } else {
                int res = reader.compareSub(l, mid-1, mid+1, r);
                if (res == 1) r = mid - 1;
                else if (res == -1) l = mid + 1;
                else return mid;
            }
        }
        return l;
    }
}
 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

// interface ArrayReader {
//     fun compareSub(l: Int, r: Int, x: Int, y: Int): Int
//     fun length(): Int
// }
class Solution {
    fun getIndex(reader: ArrayReader): Int {
        var l = 0
        var r = reader.length() - 1
        while (l < r) {
            val len = r - l + 1
            val mid = l + (r - l) / 2
            if (len % 2 == 0) {
                val res = reader.compareSub(l, mid, mid+1, r)
                if (res == 1) r = mid
                else l = mid + 1
            } else {
                val res = reader.compareSub(l, mid-1, mid+1, r)
                if (res == 1) r = mid - 1
                else if (res == -1) l = mid + 1
                else return mid
            }
        }
        return l
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# class ArrayReader:
#     def compareSub(self, l: int, r: int, x: int, y: int) -> int: ...
#     def length(self) -> int: ...
class Solution:
    def getIndex(self, reader: 'ArrayReader') -> int:
        l, r = 0, reader.length() - 1
        while l < r:
            length = r - l + 1
            mid = l + (r - l) // 2
            if length % 2 == 0:
                res = reader.compareSub(l, mid, mid+1, r)
                if res == 1:
                    r = mid
                else:
                    l = mid + 1
            else:
                res = reader.compareSub(l, mid-1, mid+1, r)
                if res == 1:
                    r = mid - 1
                elif res == -1:
                    l = mid + 1
                else:
                    return mid
        return l
 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

// trait ArrayReader {
//     fn compare_sub(&self, l: i32, r: i32, x: i32, y: i32) -> i32;
//     fn length(&self) -> i32;
// }
impl Solution {
    pub fn get_index(reader: &impl ArrayReader) -> i32 {
        let mut l = 0;
        let mut r = reader.length() - 1;
        while l < r {
            let len = r - l + 1;
            let mid = l + (r - l) / 2;
            if len % 2 == 0 {
                let res = reader.compare_sub(l, mid, mid+1, r);
                if res == 1 {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            } else {
                let res = reader.compare_sub(l, mid-1, mid+1, r);
                if res == 1 {
                    r = mid - 1;
                } else if res == -1 {
                    l = mid + 1;
                } else {
                    return mid;
                }
            }
        }
        l
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// interface ArrayReader {
//     compareSub(l: number, r: number, x: number, y: number): number;
//     length(): number;
// }
class Solution {
    getIndex(reader: ArrayReader): number {
        let l = 0, r = reader.length() - 1;
        while (l < r) {
            const len = r - l + 1, mid = l + ((r - l) >> 1);
            if (len % 2 === 0) {
                const res = reader.compareSub(l, mid, mid+1, r);
                if (res === 1) r = mid;
                else l = mid + 1;
            } else {
                const res = reader.compareSub(l, mid-1, mid+1, r);
                if (res === 1) r = mid - 1;
                else if (res === -1) l = mid + 1;
                else return mid;
            }
        }
        return l;
    }
}

Complexity

  • ⏰ Time complexity: O(log n), as each compare halves the search space.
  • 🧺 Space complexity: O(1), as only a few variables are used.