MediumNo. 1533LeetCode Premium
Find the Index of the Large Integer — LeetCode 1533 Python Solution
- Pattern
- Monotonic Stack
- Topics
- Array, Binary Search, Interactive
- 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
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
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
| No. | Problem | Difficulty |
|---|---|---|
| 1095 | Find in Mountain Array | Hard |
| 1539 | Kth Missing Positive Number | Easy |
| 0004 | Median of Two Sorted Arrays | Hard |
| 0033 | Search in Rotated Sorted Array | Medium |
| 0034 | Find First and Last Position of Element in Sorted Array | Medium |
| 0035 | Search Insert Position | Easy |
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.