Button with Longest Push Time

Difficulty: Easy | Acceptance: 41.10% | Paid: No Topics: Array

You are given a 0-indexed integer array pushTime of length n, where pushTime[i] represents the duration (in seconds) that the i-th button is held down. Return the index of the button that was held down for the longest time. If there is a tie, return the smallest index.

• Examples
• Constraints
• Linear Scan
• Sorting with Index Tracking
• Max Heap (Priority Queue)

Examples

Example 1

Input:

events = [[1,2],[2,5],[3,9],[1,15]]

Output:

1

Explanation: Button with index 1 is pressed at time 2.

Button with index 2 is pressed at time 5, so it took 5 - 2 = 3 units of time.

Button with index 3 is pressed at time 9, so it took 9 - 5 = 4 units of time.

Button with index 1 is pressed again at time 15, so it took 15 - 9 = 6 units of time.

Example 2

Input:

events = [[10,5],[1,7]]

Output:

10

Explanation: Button with index 10 is pressed at time 5.

Button with index 1 is pressed at time 7, so it took 7 - 5 = 2 units of time.

Constraints

- 1 <= events.length <= 1000
- events[i] == [indexi, timei]
- 1 <= indexi, timei <= 10^5
- The input is generated such that events is sorted in increasing order of timei.

Linear Scan

Intuition We can iterate through the array once, keeping track of the maximum value found so far and its corresponding index. If we find a value strictly greater than the current maximum, we update both the maximum value and the index. If we find a value equal to the current maximum, we do nothing to preserve the smallest index.

Steps

• Initialize maxVal to -1 (or Integer.MIN_VALUE / INT_MIN) and maxIdx to 0.
• Iterate through the array using a loop.
• For each element pushTime[i]:
  • If pushTime[i] > maxVal, update maxVal = pushTime[i] and maxIdx = i.
• Return maxIdx.

class Solution:
    def buttonWithLongestPushTime(self, pushTime: list[int]) -> int:
        max_val = -1
        max_idx = 0
        for i, time in enumerate(pushTime):
            if time > max_val:
                max_val = time
                max_idx = i
        return max_idx

Complexity

• Time: O(n)
• Space: O(1)
• Notes: This is the most optimal approach as it only requires a single pass through the array.

Sorting with Index Tracking

Intuition We can create an array of pairs (or objects) containing the value and its original index. By sorting this array in descending order based on the value, the first element will hold the maximum value. We then return the index associated with this first element. Since standard sort is stable or we can define a comparator that handles ties by index, we ensure the correct result.

Steps

• Create a list/array of objects/tuples storing (value, index).
• Sort the list in descending order of value. If values are equal, sort by index in ascending order.
• Return the index of the first element in the sorted list.

class Solution:
    def buttonWithLongestPushTime(self, pushTime: list[int]) -> int:
        # Create list of (value, index)
        indexed_times = [(val, i) for i, val in enumerate(pushTime)]
        # Sort by value descending, then index ascending
        indexed_times.sort(key=lambda x: (-x[0], x[1]))
        return indexed_times[0][1]

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Sorting is slower than a linear scan and requires extra space to store indices.

Max Heap (Priority Queue)

Intuition We can insert all elements into a Max-Heap (Priority Queue) along with their indices. The element at the top of the heap will be the one with the maximum value. We pop the top element and return its index. To handle ties correctly (smallest index), we ensure that if values are equal, the smaller index is prioritized in the heap ordering.

Steps

• Initialize a Max-Heap.
• Push all (value, index) pairs into the heap. The heap comparator should prioritize higher values, and for equal values, smaller indices.
• Pop the top element from the heap.
• Return the index of the popped element.

import heapq

class Solution:
    def buttonWithLongestPushTime(self, pushTime: list[int]) -> int:
        # Python heapq is a min-heap, so we store (-value, index)
        heap = []
        for i, val in enumerate(pushTime):
            heapq.heappush(heap, (-val, i))
        
        # The top of the heap is the max value (smallest negative)
        # If values are equal, the smaller index comes first naturally in tuple comparison
        return heap[0][1]

Complexity

• Time: O(n log n)
• Space: O(n)
• Notes: Using a heap is overkill for this problem as it requires O(n log n) time and O(n) space, whereas a linear scan is O(n) time and O(1) space.