Find the Index of the Large Integer — LeetCode 1533 Python Solution
- Problem
- #1533
- Pattern
- Monotonic Stack
- Reading time
- 6 min
- Source
- leetcode.com
The 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.
Example
- Input
- arr = [7,7,7,7,10,7,7,7]
- Output
- 4
- Explanation
- The following calls to the API
Python solution
# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
# class ArrayReader(object):
# # Compares the sum of arr[l..r] with the sum of arr[x..y]
# # return 1 if sum(arr[l..r]) > sum(arr[x..y])
# # return 0 if sum(arr[l..r]) == sum(arr[x..y])
# # return -1 if sum(arr[l..r]) < sum(arr[x..y])
# def compareSub(self, l: int, r: int, x: int, y: int) -> int:
#
# # Returns the length of the array
# def length(self) -> int:
#
class Solution:
def getIndex(self, reader: 'ArrayReader') -> int:
left, right = 0, reader.length() - 1
while left < right:
t1, t2, t3 = (
left,
left + (right - left) // 3,
left + ((right - left) // 3) * 2 + 1,
)
cmp = reader.compareSub(t1, t2, t2 + 1, t3)
if cmp == 0:
left = t3 + 1
elif cmp == 1:
right = t2
else:
left, right = t2 + 1, t3
return leftComplexity
| Measure | Complexity |
|---|---|
| Time | O(log n) or O(n log n) |
| Space | O(1) auxiliary |
Pattern: Monotonic Stack
Answer "what is the next greater element" for every position in one pass. LeetCode 1533. Find the Index of the Large Integer is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1533. Find the Index of the Large Integer?
- LeetCode 1533. Find the Index of the Large Integer is rated Medium on LeetCode.
- What topics does LeetCode 1533. Find the Index of the Large Integer cover?
- LeetCode 1533. Find the Index of the Large Integer is tagged Array, Binary Search and Interactive on LeetCode.
- Is LeetCode 1533. Find the Index of the Large Integer a premium problem?
- Yes. LeetCode 1533. Find the Index of the Large Integer is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.