algorithms/leetcode/2113-ElementsInArrayAfterRemovingAndReplacingElements.go at master · freewu/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package main

// 2113. Elements in Array After Removing and Replacing Elements
// You are given a 0-indexed integer array nums.
// Initially on minute 0, the array is unchanged.
// Every minute, the leftmost element in nums is removed until no elements remain.
// Then, every minute, one element is appended to the end of nums, in the order they were removed in, until the original array is restored.
// This process repeats indefinitely.

//     For example, the array [0,1,2] would change as follows:
//         [0,1,2] → [1,2] → [2] → [] → [0] → [0,1] → [0,1,2] → [1,2] → [2] → [] → [0] → [0,1] → [0,1,2] → ...

// You are also given a 2D integer array queries of size n where queries[j] = [timej, indexj].
// The answer to the jth query is:
//     1. nums[indexj] if indexj < nums.length at minute timej
//     2. -1 if indexj >= nums.length at minute timej

// Return an integer array ans of size n where ans[j] is the answer to the jth query.

// Example 1:
// Input: nums = [0,1,2], queries = [[0,2],[2,0],[3,2],[5,0]]
// Output: [2,2,-1,0]
// Explanation:
// Minute 0: [0,1,2] - All elements are in the nums.
// Minute 1: [1,2]   - The leftmost element, 0, is removed.
// Minute 2: [2]     - The leftmost element, 1, is removed.
// Minute 3: []      - The leftmost element, 2, is removed.
// Minute 4: [0]     - 0 is added to the end of nums.
// Minute 5: [0,1]   - 1 is added to the end of nums.
// At minute 0, nums[2] is 2.
// At minute 2, nums[0] is 2.
// At minute 3, nums[2] does not exist.
// At minute 5, nums[0] is 0.

// Example 2:
// Input: nums = [2], queries = [[0,0],[1,0],[2,0],[3,0]]
// Output: [2,-1,2,-1]
// Minute 0: [2] - All elements are in the nums.
// Minute 1: []  - The leftmost element, 2, is removed.
// Minute 2: [2] - 2 is added to the end of nums.
// Minute 3: []  - The leftmost element, 2, is removed.
// At minute 0, nums[0] is 2.
// At minute 1, nums[0] does not exist.
// At minute 2, nums[0] is 2.
// At minute 3, nums[0] does not exist.

// Constraints:
//     1 <= nums.length <= 100
//     0 <= nums[i] <= 100
//     n == queries.length
//     1 <= n <= 10^5
//     queries[j].length == 2
//     0 <= timej <= 10^5
//     0 <= indexj < nums.length

import "fmt"

func elementInNums(nums []int, queries [][]int) []int {
    res, n := []int{}, len(nums)
    for _, query := range queries {
        time, index := query[0], query[1]
        m := time % (2 * n)
        if m == n{
            res = append(res, -1)
        } else if m < n {
            if index < n - m {
                res = append(res, nums[m + index])
            } else {
                res = append(res,-1)
            }
        } else {
            if index < m - n{
                res = append(res, nums[index])
            } else {
                res = append(res, -1)
            }
        }
    }
    return res
}

func elementInNums1(nums []int, queries [][]int) []int {
    res, n := make([]int, len(queries)), len(nums)
    query := func(time int, j int) int {
        time %= 2 * n
        if time <= n {
            if j < n - time {
                return nums[time + j]
            } else {
                return -1
            }
        }
        if j < time - n {
            return nums[j]
        }
        return -1
    }
    for i, q := range queries {
        res[i] = query(q[0], q[1])
    }
    return res
}

func main() {
    // Example 1:
    // Input: nums = [0,1,2], queries = [[0,2],[2,0],[3,2],[5,0]]
    // Output: [2,2,-1,0]
    // Explanation:
    // Minute 0: [0,1,2] - All elements are in the nums.
    // Minute 1: [1,2]   - The leftmost element, 0, is removed.
    // Minute 2: [2]     - The leftmost element, 1, is removed.
    // Minute 3: []      - The leftmost element, 2, is removed.
    // Minute 4: [0]     - 0 is added to the end of nums.
    // Minute 5: [0,1]   - 1 is added to the end of nums.
    // At minute 0, nums[2] is 2.
    // At minute 2, nums[0] is 2.
    // At minute 3, nums[2] does not exist.
    // At minute 5, nums[0] is 0.
    fmt.Println(elementInNums([]int{0,1,2}, [][]int{{0,2},{2,0},{3,2},{5,0}})) // [2,2,-1,0]
    // Example 2:
    // Input: nums = [2], queries = [[0,0],[1,0],[2,0],[3,0]]
    // Output: [2,-1,2,-1]
    // Minute 0: [2] - All elements are in the nums.
    // Minute 1: []  - The leftmost element, 2, is removed.
    // Minute 2: [2] - 2 is added to the end of nums.
    // Minute 3: []  - The leftmost element, 2, is removed.
    // At minute 0, nums[0] is 2.
    // At minute 1, nums[0] does not exist.
    // At minute 2, nums[0] is 2.
    // At minute 3, nums[0] does not exist.
    fmt.Println(elementInNums([]int{2}, [][]int{{0,0},{1,0},{2,0},{3,0}})) // [2,-1,2,-1]

    fmt.Println(elementInNums1([]int{0,1,2}, [][]int{{0,2},{2,0},{3,2},{5,0}})) // [2,2,-1,0]
    fmt.Println(elementInNums1([]int{2}, [][]int{{0,0},{1,0},{2,0},{3,0}})) // [2,-1,2,-1]
}