3237. Alt and Tab Simulation 🔒

Description

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

Solutions

Solution 1: Hash Table + Reverse Traversal

According to the problem description, the later the query, the earlier it appears in the result. Therefore, we can traverse the $\textit{queries}$ array in reverse order, using a hash table $\textit{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 $\textit{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 $\textit{windows}$ and $\textit{queries}$ arrays, respectively.

Python3JavaC++GoTypeScript

class Solution:
    def simulationResult(self, windows: List[int], queries: List[int]) -> List[int]:
        s = set()
        ans = []
        for q in queries[::-1]:
            if q not in s:
                ans.append(q)
                s.add(q)
        for w in windows:
            if w not in s:
                ans.append(w)
        return ans

class Solution {
    public int[] simulationResult(int[] windows, int[] queries) {
        int n = windows.length;
        boolean[] s = new boolean[n + 1];
        int[] ans = new int[n];
        int k = 0;
        for (int i = queries.length - 1; i >= 0; --i) {
            int q = queries[i];
            if (!s[q]) {
                ans[k++] = q;
                s[q] = true;
            }
        }
        for (int w : windows) {
            if (!s[w]) {
                ans[k++] = w;
            }
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> simulationResult(vector<int>& windows, vector<int>& queries) {
        int n = windows.size();
        vector<bool> s(n + 1);
        vector<int> ans;
        for (int i = queries.size() - 1; ~i; --i) {
            int q = queries[i];
            if (!s[q]) {
                s[q] = true;
                ans.push_back(q);
            }
        }
        for (int w : windows) {
            if (!s[w]) {
                ans.push_back(w);
            }
        }
        return ans;
    }
};

func simulationResult(windows []int, queries []int) (ans []int) {
    n := len(windows)
    s := make([]bool, n+1)
    for i := len(queries) - 1; i >= 0; i-- {
        q := queries[i]
        if !s[q] {
            s[q] = true
            ans = append(ans, q)
        }
    }
    for _, w := range windows {
        if !s[w] {
            ans = append(ans, w)
        }
    }
    return
}

function simulationResult(windows: number[], queries: number[]): number[] {
    const n = windows.length;
    const s: boolean[] = Array(n + 1).fill(false);
    const ans: number[] = [];
    for (let i = queries.length - 1; i >= 0; i--) {
        const q = queries[i];
        if (!s[q]) {
            s[q] = true;
            ans.push(q);
        }
    }
    for (const w of windows) {
        if (!s[w]) {
            ans.push(w);
        }
    }
    return ans;
}

Comments