Button with Longest Push Time - LeetCode Solution

In this blog post, we will solve the LeetCode question "Button with Longest Push Time" step by step. We'll start with a brute-force approach, optimize it, and then provide implementations in C++, Java, and Python. Let's also analyze the time complexity and space complexity for each approach.

Problem Description

You are given a 2D array events where:

• events[i] = [indexi, timei] represents that the button at indexi was pressed at timei.

The array is sorted in increasing order of time.

Objective: Find the index of the button that took the longest time to press. If multiple buttons have the same longest time, return the button with the smallest index.

Example 1:

Input:

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

Output:

1

Explanation:

• Button 1: Time = 2 (first button press).

• Button 2: Time = 5 - 2 = 3.

• Button 3: Time = 9 - 5 = 4.

• Button 1: Time = 15 - 9 = 6.

The longest press time is 6, which belongs to button 1.

Example 2:

Input:

[[10,5],[1,7]]

Output:

10

Explanation:

• Button 10: Time = 5.

• Button 1: Time = 7 - 5 = 2.

The longest press time is 5, which belongs to button 10.

Constraints:

• 1 <= events.length <= 1000

• 1 <= indexi, timei <= 10^5

• The input is sorted by timei.

---

Brute-Force Approach

Algorithm:

1. Iterate through the events array.

2. For each event, calculate the time difference between consecutive button presses.

3. Keep track of the button with the longest press time. In case of a tie, pick the button with the smallest index.

Code Implementation (Brute-Force)

C++ Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int buttonWithLongestTime(vector<vector<int>>& events) {
        int longestTime = events[0][1];
        int longestButton = events[0][0];

        for (int i = 1; i < events.size(); i++) {
            int duration = events[i][1] - events[i - 1][1];

            if (duration > longestTime || (duration == longestTime && events[i][0] < longestButton)) {
                longestTime = duration;
                longestButton = events[i][0];
            }
        }

        return longestButton;
    }
};

Java Code

class Solution {
    public int buttonWithLongestTime(int[][] events) {
        int longestTime = events[0][1];
        int longestButton = events[0][0];

        for (int i = 1; i < events.length; i++) {
            int duration = events[i][1] - events[i - 1][1];

            if (duration > longestTime || (duration == longestTime && events[i][0] < longestButton)) {
                longestTime = duration;
                longestButton = events[i][0];
            }
        }

        return longestButton;
    }
}

Python Code

def buttonWithLongestTime(events):
    longest_time = events[0][1]
    longest_button = events[0][0]

    for i in range(1, len(events)):
        duration = events[i][1] - events[i - 1][1]

        if duration > longest_time or (duration == longest_time and events[i][0] < longest_button):
            longest_time = duration
            longest_button = events[i][0]

    return longest_button

Complexity Analysis

• Time Complexity:

  • O(n): We iterate through the events array once.

• Space Complexity:

  • O(1): No extra space is used apart from variables.

---

Optimized Approach

Since the brute-force solution is already efficient with O(n) complexity, we don't need further optimization. However, we can ensure the solution is clean and concise while maintaining clarity.

Key Points:

• One Pass: Iterate through the array and update longestTime and longestButton during the iteration.

• Tie-Breaking: Use conditions to handle ties when multiple buttons have the same press duration.

The code implementations above are already optimized for the given constraints.

---

In this problem, we learned how to calculate the button with the longest press time by iterating through the sorted events array. The solution is straightforward and operates in O(n) time, making it optimal for the input size.

Tags

• LeetCode

• Data Structures and Algorithms

• Array Problems

• Time Complexity O(n)

• Space Complexity O(1)

• Programming Interview Questions

---

Tips for Interviews

1. Explain Your Approach: Clearly explain how you calculated the press durations and handled ties.

2. Edge Cases: Mention handling edge cases like single-element arrays.

3. Justify Complexity: Ensure the interviewer understands why your solution is O(n).