Watch 10 video solutions for Alt and Tab Simulation, a medium level problem involving Array, Hash Table, Simulation. This walkthrough by Greg Hogg has 2,093,954 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |