LeetCode 3237 - Alt and Tab Simulation

LeetCode Problem 3237

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Simulation

Solution

Problem Understanding

The problem asks us to simulate the behavior of switching between open windows using the classic Alt + Tab operation.

We are given an array called windows, which represents the current ordering of open windows. The first element of the array is the window currently on top, and the last element is the window at the bottom.

We are also given another array called queries. Each query represents a window that is selected and brought to the top of the stack. When a window is brought to the top:

• That window is removed from its current position.
• It is inserted at the beginning of the array.
• The relative order of all other windows remains unchanged.

The task is to process every query in order and return the final arrangement of the windows.

For example, suppose the current order is:

[1, 2, 3]

If we bring window 3 to the top, the result becomes:

[3, 1, 2]

If we bring 3 to the top again, nothing changes because it is already on top.

The constraints are important:

• n can be as large as 100000
• The number of queries can also be as large as 100000

These limits immediately tell us that an inefficient simulation may be too slow. Any approach with quadratic complexity, such as repeatedly shifting large portions of the array for every query, can become problematic.

The problem also guarantees that:

• windows is a permutation of [1, n]
• Every window ID is unique
• Every query refers to a valid window

This means we never need to worry about duplicate windows or invalid queries.

Several edge cases are worth noticing early:

• A query may repeatedly reference the same window.
• A queried window may already be at the top.
• There may be only one window.
• Every query could move a different window to the front.
• The number of queries may be much larger than the number of windows.

These cases can expose inefficiencies or incorrect ordering logic in a naive implementation.

Approaches

Brute Force Simulation

The most direct solution is to literally simulate the process exactly as described.

For every query:

1. Find the queried window in the array.
2. Remove it from its current position.
3. Insert it at the beginning.

This approach is correct because it follows the problem statement precisely.

However, the expensive part is locating and shifting elements inside the array. In the worst case:

• Searching for the window costs O(n)
• Removing and inserting also costs O(n)

Since there can be up to 100000 queries, the total complexity becomes O(n * q).

With both values potentially equal to 100000, this can require around 10^10 operations, which is far too slow.

Optimal Observation

The key observation is that only the relative ordering of recently queried windows matters.

Suppose we process the queries from left to right:

• Whenever a window is queried for the first time, it eventually appears closer to the front than all windows that were never queried afterward.
• Repeated queries for the same window do not create additional copies.
• The final front portion of the answer is simply the distinct queried windows, ordered by their most recent appearance.

Instead of repeatedly modifying the array, we can reconstruct the final order directly.

The idea is:

1. Process queries from the end toward the beginning.
2. Collect each window the first time we encounter it.
3. These windows form the front portion of the final ordering.
4. Append all remaining windows from the original array that were never added.

This works because the last query affecting a window determines its final relative position near the front.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × q)	O(1)	Simulates every move directly
Optimal	O(n + q)	O(n)	Uses reverse query processing and a hash set

Algorithm Walkthrough

Optimal Algorithm

1. Create an empty hash set called seen.

This set keeps track of which windows have already been added to the final answer. We use a hash set because membership checks are O(1) on average. 2. Create an empty list called result_front.

This list will store the windows that appear near the front after all queries are processed. 3. Traverse the queries array from right to left.

We go backward because the most recent query determines the final position of a window. 4. For each queried window:

• If the window has not been seen before:

• Add it to seen

• Append it to result_front

We only keep the most recent occurrence of each window. 5. Reverse result_front.

Since we processed queries backward, reversing restores the correct front-to-back order. 6. Traverse the original windows array.

For every window not already in seen, append it to the result.

These windows were never moved after their original placement, so their relative order remains unchanged. 7. Return the completed result array.

Why it works

The crucial invariant is that the last query involving a window determines its final position relative to all other queried windows.

By scanning queries backward, the first time we encounter a window corresponds exactly to its last movement to the top during forward execution.

All windows that never appear in the final distinct query order remain in their original relative order behind the moved windows.

Therefore, reconstructing the array in this way exactly matches the true simulation result.

Python Solution

from typing import List

class Solution:
    def simulationResult(self, windows: List[int], queries: List[int]) -> List[int]:
        seen = set()
        moved_windows = []

        # Process queries from right to left
        for window in reversed(queries):
            if window not in seen:
                seen.add(window)
                moved_windows.append(window)

        # Reverse to restore correct order
        moved_windows.reverse()

        result = moved_windows[:]

        # Append windows that were never moved
        for window in windows:
            if window not in seen:
                result.append(window)

        return result

The implementation closely follows the algorithm described earlier.

We first create a hash set named seen to track windows that have already been processed. This prevents duplicates when the same window appears multiple times in queries.

Next, we iterate through queries in reverse order. The first time we encounter a window during this reverse traversal corresponds to the last time that window was moved to the top in the original simulation.

Each unique queried window is added to moved_windows.

After the reverse traversal completes, we reverse moved_windows itself because we want the final ordering from front to back.

Finally, we append all windows from the original windows array that were never moved. Since these windows were unaffected by later operations, they preserve their original relative order.

The resulting array is the final state after all operations.

Go Solution

func simulationResult(windows []int, queries []int) []int {
	seen := make(map[int]bool)
	movedWindows := []int{}

	// Process queries from right to left
	for i := len(queries) - 1; i >= 0; i-- {
		window := queries[i]

		if !seen[window] {
			seen[window] = true
			movedWindows = append(movedWindows, window)
		}
	}

	// Reverse movedWindows
	for left, right := 0, len(movedWindows)-1; left < right; {
		movedWindows[left], movedWindows[right] =
			movedWindows[right], movedWindows[left]

		left++
		right--
	}

	result := make([]int, 0, len(windows))

	// Add moved windows first
	result = append(result, movedWindows...)

	// Add untouched windows
	for _, window := range windows {
		if !seen[window] {
			result = append(result, window)
		}
	}

	return result
}

The Go implementation uses a map[int]bool instead of a Python set.

Slices are used to store both the moved windows and the final result. Since Go does not provide a built-in reverse function for slices, we manually reverse the slice using a two-pointer swap loop.

There are no integer overflow concerns because all values are comfortably within standard integer limits.

The logic otherwise mirrors the Python solution exactly.

Worked Examples

Example 1

Input:

windows = [1, 2, 3]
queries = [3, 3, 2]

We process queries from right to left.

Step	Current Query	Seen	moved_windows
Start	-	{}	[]
1	2	{2}	[2]
2	3	{2, 3}	[2, 3]
3	3	{2, 3}	[2, 3]

Now reverse moved_windows:

[3, 2] -> [2, 3]

Next, append untouched windows from the original array.

Window	In Seen?	Result
1	No	[2, 3, 1]
2	Yes	[2, 3, 1]
3	Yes	[2, 3, 1]

Final answer:

[2, 3, 1]

Example 2

Input:

windows = [1, 4, 2, 3]
queries = [4, 1, 3]

Process queries from right to left.

Step	Current Query	Seen	moved_windows
Start	-	{}	[]
1	3	{3}	[3]
2	1	{1, 3}	[3, 1]
3	4	{1, 3, 4}	[3, 1, 4]

Reverse:

[3, 1, 4] -> [4, 1, 3]

Actually, note carefully that the list was built in reverse processing order:

moved_windows before reverse = [3, 1, 4]
after reverse = [4, 1, 3]

Now append untouched windows.

Window	In Seen?	Result
1	Yes	[4, 1, 3]
4	Yes	[4, 1, 3]
2	No	[4, 1, 3, 2]
3	Yes	[4, 1, 3, 2]

At this point we notice something important.

The correct final ordering from direct simulation is:

[3, 1, 4, 2]

This reveals that the correct construction is actually the reverse traversal order without reversing again.

So the final implementation should append directly from reverse traversal order.

Let us correct the logic:

Processing from right to left:

queries = [4, 1, 3]
reverse traversal = 3, 1, 4

The front order should therefore be:

[3, 1, 4]

Appending untouched windows:

[3, 1, 4, 2]

This matches the expected answer.

Therefore, we should not reverse the collected list.

Corrected Python Solution

from typing import List

class Solution:
    def simulationResult(self, windows: List[int], queries: List[int]) -> List[int]:
        seen = set()
        result = []

        # Most recent queries should appear first
        for window in reversed(queries):
            if window not in seen:
                seen.add(window)
                result.append(window)

        # Add untouched windows
        for window in windows:
            if window not in seen:
                result.append(window)

        return result

Corrected Go Solution

func simulationResult(windows []int, queries []int) []int {
	seen := make(map[int]bool)
	result := []int{}

	// Process queries from right to left
	for i := len(queries) - 1; i >= 0; i-- {
		window := queries[i]

		if !seen[window] {
			seen[window] = true
			result = append(result, window)
		}
	}

	// Append untouched windows
	for _, window := range windows {
		if !seen[window] {
			result = append(result, window)
		}
	}

	return result
}

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + q)	Each window and query is processed at most once
Space	O(n)	The hash set stores up to n windows

The algorithm is linear because every query is checked exactly once, and every window in the original array is also processed once.

Hash set operations are constant time on average, so no nested iteration occurs.

The additional memory comes from storing the seen set and the result array.

Test Cases

sol = Solution()

# Provided example 1
assert sol.simulationResult([1, 2, 3], [3, 3, 2]) == [2, 3, 1]

# Provided example 2
assert sol.simulationResult([1, 4, 2, 3], [4, 1, 3]) == [3, 1, 4, 2]

# Single window
assert sol.simulationResult([1], [1]) == [1]

# No effective change because top window queried repeatedly
assert sol.simulationResult([1, 2, 3], [1, 1, 1]) == [1, 2, 3]

# Every window queried exactly once
assert sol.simulationResult([1, 2, 3, 4], [4, 3, 2, 1]) == [1, 2, 3, 4]

# Queries with duplicates
assert sol.simulationResult([1, 2, 3, 4], [2, 4, 2]) == [2, 4, 1, 3]

# Large movement toward front
assert sol.simulationResult([5, 4, 3, 2, 1], [1]) == [1, 5, 4, 3, 2]

# Windows never queried remain ordered
assert sol.simulationResult([1, 2, 3, 4, 5], [5, 3]) == [3, 5, 1, 2, 4]

# Repeated alternating queries
assert sol.simulationResult([1, 2, 3], [2, 3, 2, 3]) == [3, 2, 1]

# Already optimal ordering
assert sol.simulationResult([3, 2, 1], [3]) == [3, 2, 1]

Test	Why
[1,2,3], [3,3,2]	Validates repeated queries
[1,4,2,3], [4,1,3]	Standard mixed movement case
[1], [1]	Smallest valid input
[1,2,3], [1,1,1]	Repeated top-window queries
[1,2,3,4], [4,3,2,1]	Every window moved
[1,2,3,4], [2,4,2]	Duplicate query handling
[5,4,3,2,1], [1]	Bottom window moved to top
[1,2,3,4,5], [5,3]	Preserving untouched order
[1,2,3], [2,3,2,3]	Alternating repeated moves
[3,2,1], [3]	Querying current top window

Edge Cases

One important edge case occurs when the same window is queried repeatedly. A naive implementation may accidentally insert duplicates into the final ordering if it does not track previously processed windows correctly. The hash set prevents this by ensuring each queried window is added only once during reverse traversal.

Another important case is when a queried window is already at the top. In a direct simulation, this operation changes nothing, but careless logic could unnecessarily reorder elements. The reconstruction approach naturally handles this because the window simply appears once in the final queried order.

A third edge case involves windows that are never queried. These windows must preserve their original relative order. This detail is easy to overlook if the implementation only focuses on queried windows. By iterating through the original windows array at the end and appending unseen elements in order, the algorithm guarantees correct preservation of untouched windows.