# Button with Longest Push Time
**Difficulty:** EASY
[External](https://leetcode.com/problems/button-with-longest-push-time)
Canonical: https://scaleengineer.com/dsa/problems/button-with-longest-push-time
**Data structures:** Array
**Companies:** [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
You are given a 2D array `events` which represents a sequence of events where a child pushes a series of buttons on a keyboard.

Each `events[i] = [indexi, timei]` indicates that the button at index `indexi` was pressed at time `timei`.

* The array is **sorted** in increasing order of `time`.
* The time taken to press a button is the difference in time between consecutive button presses. The time for the first button is simply the time at which it was pressed.

Return the `index` of the button that took the **longest** time to push. If multiple buttons have the same longest time, return the button with the **smallest** `index`.

**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 <= 105`
* The input is generated such that `events` is sorted in increasing order of `timei`.

# Approaches
## Two-Pass Approach with Extra Space
This approach involves two main steps. First, we iterate through the `events` array to calculate the duration of each button push and store these durations along with their corresponding button indices. In the second step, we iterate through the stored data to find the button with the longest push time, handling ties by choosing the smaller index.
**Time:** O(N), where N is the number of events. The first loop takes O(N) and the second loop also takes O(N). O(N) + O(N) = O(N). · **Space:** O(N), where N is the number of events. We use an auxiliary array of size N to store the durations and indices.
**Pros:** The logic is separated into two distinct, easy-to-understand steps: calculation and processing.; It correctly solves the problem.
**Cons:** It is not space-optimal as it requires O(N) extra space.; It requires two passes over the data (or data derived from it), which is less efficient than a single-pass solution.
### Explanation
We can use a list of pairs or a 2D array to store the calculated `(duration, index)` for each event.

We initialize a `previousTime` variable to 0. We loop through the input `events` array. For each event, we calculate the duration as `currentTime - previousTime`. We then add a new pair `(duration, buttonIndex)` to our auxiliary storage. After processing the event, we update `previousTime` to `currentTime` for the next iteration.

After the first loop populates our storage, we initialize `maxDuration` and `resultIndex`. We then loop through our stored `(duration, index)` pairs. In this loop, we compare each duration with `maxDuration`.

- If the current duration is greater than `maxDuration`, we update `maxDuration` and set `resultIndex` to the current index.
- If the current duration is equal to `maxDuration`, we update `resultIndex` only if the current index is smaller than the existing `resultIndex`, as per the tie-breaking rule.

Finally, we return the `resultIndex`.

```java
class Solution {
    public int longestPush(int[][] events) {
        if (events.length == 0) {
            return -1; // Should not happen based on constraints
        }

        // Use a 2D array to store [duration, index] for each event
        int[][] durations = new int[events.length][2];
        int previousTime = 0;

        // First pass: calculate and store all durations
        for (int i = 0; i < events.length; i++) {
            int index = events[i][0];
            int time = events[i][1];
            int duration = time - previousTime;
            durations[i][0] = duration;
            durations[i][1] = index;
            previousTime = time;
        }

        // Second pass: find the longest duration and corresponding index
        int longestDuration = -1;
        int resultIndex = -1;

        for (int i = 0; i < durations.length; i++) {
            int duration = durations[i][0];
            int index = durations[i][1];
            if (duration > longestDuration) {
                longestDuration = duration;
                resultIndex = index;
            } else if (duration == longestDuration) {
                if (index < resultIndex) {
                    resultIndex = index;
                }
            }
        }

        return resultIndex;
    }
}
```
### Algorithm
- Create an auxiliary array `durations` of size `N x 2` to store `[duration, index]`.
- Initialize `previousTime = 0`.
- Iterate through the `events` array from `i = 0` to `N-1`:
  - Calculate `duration = events[i][1] - previousTime`.
  - Store `duration` and `events[i][0]` in the `durations` array at index `i`.
  - Update `previousTime = events[i][1]`.
- Initialize `longestDuration = -1` and `resultIndex = -1`.
- Iterate through the `durations` array:
  - If the current `duration` is greater than `longestDuration`, update `longestDuration` and `resultIndex`.
  - If the current `duration` equals `longestDuration`, update `resultIndex` to the minimum of the current `resultIndex` and the current `index`.
- Return `resultIndex`.

## Single-Pass Iteration (Optimal)
This is the most efficient approach. We can solve the problem by iterating through the `events` array just once. We maintain variables to keep track of the longest duration found so far and the corresponding button index. As we iterate, we calculate the duration for each event and update our tracking variables if we find a longer duration or a tie with a smaller button index.
**Time:** O(N), where N is the number of events. We iterate through the input array only once. · **Space:** O(1). We only use a few variables to store the maximum duration, result index, and previous time, regardless of the input size.
**Pros:** Highly efficient in both time and space.; Optimal solution as it processes the data in a single pass with constant extra space.; The code is concise and easy to follow.
**Cons:** No significant cons for this problem. It's the ideal solution.
### Explanation
We initialize `longestDuration` to -1, `resultIndex` to -1, and `previousTime` to 0. This avoids special handling for the first element and makes the loop uniform.

We then iterate through the `events` array. In each iteration, we calculate the current push duration by subtracting `previousTime` from the current event's time.

We compare this `currentDuration` with `longestDuration`:
- If `currentDuration` is strictly greater than `longestDuration`, it means we've found a new longest push. We update `longestDuration` to `currentDuration` and `resultIndex` to the current button's index.
- If `currentDuration` is equal to `longestDuration`, we have a tie. According to the problem, we should choose the button with the smaller index. So, we update `resultIndex` to the minimum of its current value and the current button's index.

After checking, we update `previousTime` to the current event's time to prepare for the next iteration. After the loop finishes, `resultIndex` will hold the index of the button with the longest push time, with ties correctly resolved.

```java
class Solution {
    public int longestPush(int[][] events) {
        int longestDuration = -1;
        int resultIndex = -1;
        int previousTime = 0;

        for (int[] event : events) {
            int index = event[0];
            int time = event[1];
            int duration = time - previousTime;

            if (duration > longestDuration) {
                longestDuration = duration;
                resultIndex = index;
            } else if (duration == longestDuration) {
                if (index < resultIndex) {
                    resultIndex = index;
                }
            }
            previousTime = time;
        }
        return resultIndex;
    }
}
```
### Algorithm
- Initialize `longestDuration = -1`, `resultIndex = -1`, and `previousTime = 0`.
- Iterate through each `event` in the `events` array:
  - Let `currentIndex = event[0]` and `currentTime = event[1]`.
  - Calculate `duration = currentTime - previousTime`.
  - If `duration > longestDuration`:
    - Set `longestDuration = duration`.
    - Set `resultIndex = currentIndex`.
  - Else if `duration == longestDuration`:
    - Set `resultIndex = min(resultIndex, currentIndex)`.
  - Update `previousTime = currentTime`.
- Return `resultIndex`.

# Solutions
### Java

```java
class Solution { public int buttonWithLongestTime ( int [][] events ) { int ans = events [ 0 ][ 0 ], t = events [ 0 ][ 1 ]; for ( int k = 1 ; k < events . length ; ++ k ) { int i = events [ k ][ 0 ], t2 = events [ k ][ 1 ], t1 = events [ k - 1 ][ 1 ]; int d = t2 - t1 ; if ( d > t || ( d == t && ans > i )) { ans = i ; t = d ; } } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  int buttonWithLongestTime(vector<vector<int>> &events) {
    int ans = events[0][0], t = events[0][1];
    for (int k = 1; k < events.size(); ++k) {
      int i = events[k][0], t2 = events[k][1], t1 = events[k - 1][1];
      int d = t2 - t1;
      if (d > t || (d == t && ans > i)) {
        ans = i;
        t = d;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def buttonWithLongestTime ( self , events : List [ List [ int ]]) -> int : ans , t = events [ 0 ] for ( _ , t1 ), ( i , t2 ) in pairwise ( events ): d = t2 - t1 if d > t or ( d == t and i < ans ): ans , t = i , d return ans
```