Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7
8
9

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 <= 10^5
  • windows is a permutation of [1, n].
  • 1 <= queries.length <= 10^5
  • 1 <= queries[i] <= n

Solution

Method 1 – Hash Map + List Simulation

Intuition

The key idea is to efficiently move a window to the top each time a query is made. Since the window order changes dynamically, we need a way to quickly find and move any window. Using a hash map to track indices allows us to locate windows in constant time, and a list (array) lets us rearrange them efficiently.

Approach

  1. Build a hash map (idx) mapping each window value to its index in the windows list.
  2. For each query:
  • Find the index of the queried window using the hash map.
  • Remove the window from its current position and insert it at the front of the list.
  • Update the hash map for all affected windows to reflect their new indices.
  1. After all queries, return the final state of the windows list.

This approach ensures each move is efficient, and the hash map keeps index lookups fast.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
   vector<int> altTabSimulation(vector<int>& windows, vector<int>& queries) {
      unordered_map<int, int> idx;
      int n = windows.size();
      for (int i = 0; i < n; ++i) idx[windows[i]] = i;
      for (int q : queries) {
        int i = idx[q];
        if (i == 0) continue;
        int val = windows[i];
        windows.erase(windows.begin() + i);
        windows.insert(windows.begin(), val);
        for (int j = 0; j <= i; ++j) idx[windows[j]] = j;
      }
      return windows;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func altTabSimulation(windows []int, queries []int) []int {
   idx := make(map[int]int)
   for i, v := range windows {
      idx[v] = i
   }
   for _, q := range queries {
      i := idx[q]
      if i == 0 {
        continue
      }
      val := windows[i]
      windows = append(windows[:i], windows[i+1:]...)
      windows = append([]int{val}, windows...)
      for j := 0; j <= i; j++ {
        idx[windows[j]] = j
      }
   }
   return windows
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
   public List<Integer> altTabSimulation(List<Integer> windows, List<Integer> queries) {
      Map<Integer, Integer> idx = new HashMap<>();
      int n = windows.size();
      for (int i = 0; i < n; ++i) idx.put(windows.get(i), i);
      for (int q : queries) {
        int i = idx.get(q);
        if (i == 0) continue;
        int val = windows.get(i);
        windows.remove(i);
        windows.add(0, val);
        for (int j = 0; j <= i; ++j) idx.put(windows.get(j), j);
      }
      return windows;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
   fun altTabSimulation(windows: MutableList<Int>, queries: List<Int>): List<Int> {
      val idx = mutableMapOf<Int, Int>()
      for (i in windows.indices) idx[windows[i]] = i
      for (q in queries) {
        val i = idx[q]!!
        if (i == 0) continue
        val valQ = windows[i]
        windows.removeAt(i)
        windows.add(0, valQ)
        for (j in 0..i) idx[windows[j]] = j
      }
      return windows
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
   def altTabSimulation(self, windows: list[int], queries: list[int]) -> list[int]:
      idx: dict[int, int] = {v: i for i, v in enumerate(windows)}
      for q in queries:
        i = idx[q]
        if i == 0:
           continue
        val = windows[i]
        windows.pop(i)
        windows.insert(0, val)
        for j in range(i + 1):
           idx[windows[j]] = j
      return windows
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
   pub fn alt_tab_simulation(mut windows: Vec<i32>, queries: Vec<i32>) -> Vec<i32> {
      use std::collections::HashMap;
      let mut idx: HashMap<i32, usize> = windows.iter().enumerate().map(|(i, &v)| (v, i)).collect();
      for &q in &queries {
        let i = idx[&q];
        if i == 0 { continue; }
        let val = windows.remove(i);
        windows.insert(0, val);
        for j in 0..=i {
           idx.insert(windows[j], j);
        }
      }
      windows
   }
}

Complexity

  • ⏰ Time complexity: O(n * q) in the worst case (since each move can take up to O(n)), but for small queries or when queries are mostly at the front, it’s faster.
  • 🧺 Space complexity: O(n) for the hash map and window list.