There are n windows open numbered from 1 to n, we want to simulate using alt + tab to navigate between the windows.
You are given an array windows which contains the initial order of the windows (the first element is at the top and the last one is at the bottom).
You are also given an array queries where for each query, the window queries[i] is brought to the top.
Return the final state of the array windows.
Example 1:
Input: windows = [1,2,3], queries = [3,3,2]
Output: [2,3,1]
Explanation:
Here is the window array after each query:
[1,2,3][3,1,2][3,1,2][2,3,1]Example 2:
Input: windows = [1,4,2,3], queries = [4,1,3]
Output: [3,1,4,2]
Explanation:
Here is the window array after each query:
[1,4,2,3][4,1,2,3][1,4,2,3][3,1,4,2]
Constraints:
1 <= n == windows.length <= 105windows is a permutation of [1, n].1 <= queries.length <= 1051 <= queries[i] <= nProblem Overview: You are given a list of open applications and a sequence of Alt+Tab operations. Each operation switches focus to an app. The task is to compute the final ordering of apps in the Alt‑Tab switcher where the most recently accessed apps appear first.
Approach 1: Direct Simulation with Move-to-Front (O(n * q) time, O(n) space)
The straightforward approach simulates how an operating system updates the Alt‑Tab list. Maintain the apps in a list. For every query, locate the requested app using a linear scan, remove it from its current position, and insert it at the front. This mirrors the real behavior but requires shifting elements each time. Since each lookup costs O(n) and there can be q queries, the total time becomes O(n * q). Space complexity stays O(n) because only the app list is stored. This works for small inputs but becomes slow when the query list is large.
Approach 2: Hash Table + Reverse Traversal (O(n + q) time, O(n) space)
A more efficient strategy focuses on the observation that only the last occurrence of each queried app affects the final Alt‑Tab order. Traverse the query list from right to left and track apps already processed using a hash set. When an app appears for the first time in this reverse scan, append it to the result since it represents the most recent access. After processing all queries, iterate through the original apps array and append any app not yet included. The hash set guarantees O(1) membership checks, making the overall runtime O(n + q) with O(n) extra space.
This technique combines ideas from hash tables and efficient array traversal. The reverse pass ensures you only capture the most recent access for each app while preserving correct recency ordering. The remaining untouched apps keep their original relative order.
Recommended for interviews: The hash table + reverse traversal approach is what interviewers expect. It shows you recognize that only the last access matters and avoids repeated list manipulation. Mentioning the naive simulation first demonstrates understanding of the system behavior, but the optimized O(n + q) solution highlights algorithmic insight and proper use of a hash table for constant‑time lookups.
According to the problem description, the later the query, the earlier it appears in the result. Therefore, we can traverse the queries array in reverse order, using a hash table s to record the windows that have already appeared. For each query, if the current window is not in the hash table, we add it to the answer array and also add it to the hash table. Finally, we traverse the windows array again, adding the windows that are not in the hash table to the answer array.
The time complexity is O(n + m), and the space complexity is O(m). Here, n and m are the lengths of the windows and queries arrays, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation (Move-to-Front List) | O(n * q) | O(n) | When constraints are small and you want the simplest implementation |
| Hash Table + Reverse Traversal | O(n + q) | O(n) | Best general solution; avoids repeated list updates and handles large inputs efficiently |
I HATE This Coding Question, but FAANG Loves it! | Majority Element - Leetcode 169 • Greg Hogg • 2,093,954 views views
Watch 9 more video solutions →Practice Alt and Tab Simulation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor