Skip to main content
Talentd

Alt and Tab Simulation - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableSimulation8 min read
Practice this problem

Problem Statement

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:

  • Initial order: [1,2,3]
  • After the first query: [3,1,2]
  • After the second query: [3,1,2]
  • After the last query: [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:

  • Initial order: [1,4,2,3]
  • After the first query: [4,1,2,3]
  • After the second query: [1,4,2,3]
  • After the last query: [3,1,4,2]

 

Constraints:

  • 1 <= n == windows.length <= 105
  • windows is a permutation of [1, n].
  • 1 <= queries.length <= 105
  • 1 <= queries[i] <= n

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 TraversalO(n + q)O(n)Best general solution; avoids repeated list updates and handles large inputs efficiently

Video Solution

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 →

Frequently Asked Questions

Is Alt and Tab Simulation easy or hard?
Alt and Tab Simulation is typically classified as a Medium problem. The brute force simulation is easy to implement, but recognizing that only the last occurrence of each query matters is the key insight needed for the optimal O(n + q) solution.
Alt and Tab Simulation Python/Java solution
The implementation pattern is identical across languages: traverse queries in reverse, store seen apps in a hash set, append unique apps to the result, then append remaining apps from the original array. This approach translates cleanly to Python, Java, C++, Go, and TypeScript.
How to solve Alt and Tab Simulation in O(n)?
Process the queries from right to left and store seen apps in a hash set. Add an app to the result the first time it appears during this reverse scan, representing its most recent activation. After finishing the queries, append remaining apps from the original list that were never seen. This achieves O(n + q) time.
What is the best approach for Alt and Tab Simulation?
The optimal solution uses a hash table combined with reverse traversal of the query list. By scanning queries from the end and tracking which apps were already added, you capture only the most recent access for each app. This produces the correct Alt‑Tab order in O(n + q) time with O(n) extra space.
Is Alt and Tab Simulation asked at Google/Amazon/Meta?
Problems involving recency ordering, hash tables, and system behavior simulation frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem test understanding of hash sets, arrays, and efficient state updates.
What data structure is used in Alt and Tab Simulation?
The optimal solution uses a hash set (or hash table) to track which applications were already processed while traversing the queries. Arrays store the original app order and the final result, making lookups and appending efficient.
What is the time complexity of Alt and Tab Simulation?
The optimal hash table + reverse traversal solution runs in O(n + q) time, where n is the number of apps and q is the number of Alt‑Tab operations. Each app and query is processed at most once, and hash lookups are O(1) on average.

Ready to solve this problem?

Practice Alt and Tab Simulation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays