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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
/**
 * Make arr1 strictly increasing by replacing elements with elements from arr2.
 * Dynamic Programming approach.
 *
 * @param {number[]} arr1 - The array to make strictly increasing
 * @param {number[]} arr2 - The array of replacement elements
 * @return {number} - The minimum number of replacements needed, or -1 if impossible
 */
function makeArrayIncreasing(arr1, arr2) {
  // Sort arr2 and remove duplicates
  arr2 = [...new Set(arr2)].sort((a, b) => a - b);
 
  // Initialize DP map
  let dp = new Map();
 
  // Base case: first element
  dp.set(arr1[0], 0);
 
  for (const num of arr2) {
    if (num < arr1[0]) {
      dp.set(num, 1);
    }
  }
 
  // Process each position
  for (let i = 1; i < arr1.length; i++) {
    const newDp = new Map();
 
    // For each possible previous value
    for (const [prev, count] of dp.entries()) {
      // Option 1: Keep the original element
      if (arr1[i] > prev) {
        newDp.set(arr1[i], Math.min(newDp.get(arr1[i]) || Infinity, count));
      }
 
      // Option 2: Replace with an element from arr2
      const j = binarySearch(arr2, prev);
 
      if (j < arr2.length) {
        newDp.set(arr2[j], Math.min(newDp.get(arr2[j]) || Infinity, count + 1));
      }
    }
 
    // If no valid transitions, return -1
    if (newDp.size === 0) {
      return -1;
    }
 
    dp = newDp;
  }
 
  // Find the minimum number of replacements
  let minReplacements = Infinity;
 
  for (const count of dp.values()) {
    minReplacements = Math.min(minReplacements, count);
  }
 
  return minReplacements === Infinity ? -1 : minReplacements;
}
 
/**
 * Binary search to find the smallest element in arr that is greater than target.
 *
 * @param {number[]} arr - The sorted array to search in
 * @param {number} target - The target value
 * @return {number} - The index of the smallest element greater than target, or arr.length if none exists
 */
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let result = arr.length;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    if (arr[mid] > target) {
      result = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return result;
}
 
/**
 * Make arr1 strictly increasing by replacing elements with elements from arr2.
 * TreeMap approach (simulated in JavaScript).
 *
 * @param {number[]} arr1 - The array to make strictly increasing
 * @param {number[]} arr2 - The array of replacement elements
 * @return {number} - The minimum number of replacements needed, or -1 if impossible
 */
function makeArrayIncreasingTreeMap(arr1, arr2) {
  // Sort arr2 and remove duplicates
  arr2 = [...new Set(arr2)].sort((a, b) => a - b);
 
  // Initialize DP map
  let dp = new Map();
 
  // Base case: first element
  dp.set(arr1[0], 0);
 
  for (const num of arr2) {
    if (num < arr1[0]) {
      dp.set(num, 1);
    }
  }
 
  // Process each position
  for (let i = 1; i < arr1.length; i++) {
    const newDp = new Map();
    const entries = [...dp.entries()].sort((a, b) => a[0] - b[0]);
 
    for (const [prev, count] of entries) {
      // Option 1: Keep the original element
      if (arr1[i] > prev) {
        newDp.set(arr1[i], Math.min(newDp.get(arr1[i]) || Infinity, count));
      }
 
      // Option 2: Replace with an element from arr2
      for (const num of arr2) {
        if (num > prev) {
          newDp.set(num, Math.min(newDp.get(num) || Infinity, count + 1));
          break;
        }
      }
    }
 
    // If no valid transitions, return -1
    if (newDp.size === 0) {
      return -1;
    }
 
    dp = newDp;
  }
 
  // Find the minimum number of replacements
  let minReplacements = Infinity;
 
  for (const count of dp.values()) {
    minReplacements = Math.min(minReplacements, count);
  }
 
  return minReplacements === Infinity ? -1 : minReplacements;
}
 
/**
 * Make arr1 strictly increasing by replacing elements with elements from arr2.
 * Brute Force approach with memoization.
 *
 * @param {number[]} arr1 - The array to make strictly increasing
 * @param {number[]} arr2 - The array of replacement elements
 * @return {number} - The minimum number of replacements needed, or -1 if impossible
 */
function makeArrayIncreasingBruteForce(arr1, arr2) {
  // Sort arr2 and remove duplicates
  arr2 = [...new Set(arr2)].sort((a, b) => a - b);
 
  // Memoization cache
  const memo = new Map();
 
  /**
   * Recursive function to find the minimum number of replacements.
   *
   * @param {number} index - The current index in arr1
   * @param {number} prev - The previous value
   * @return {number} - The minimum number of replacements needed
   */
  function dfs(index, prev) {
    // Base case: reached the end of arr1
    if (index === arr1.length) {
      return 0;
    }
 
    // Check if we've already computed this state
    const key = `${index},${prev}`;
    if (memo.has(key)) {
      return memo.get(key);
    }
 
    // Option 1: Keep the original element if it's greater than the previous value
    let keep = Infinity;
    if (arr1[index] > prev) {
      keep = dfs(index + 1, arr1[index]);
    }
 
    // Option 2: Replace with an element from arr2
    let replace = Infinity;
    const j = binarySearch(arr2, prev);
 
    if (j < arr2.length) {
      replace = 1 + dfs(index + 1, arr2[j]);
    }
 
    // Memoize and return the minimum
    const result = Math.min(keep, replace);
    memo.set(key, result);
    return result;
  }
 
  const result = dfs(0, -Infinity);
  return result === Infinity ? -1 : result;
}
 
// Test cases
console.log(makeArrayIncreasing([1, 5, 3, 6, 7], [1, 3, 2, 4]));  // 1
console.log(makeArrayIncreasing([1, 5, 3, 6, 7], [4, 3, 1]));  // -1
console.log(makeArrayIncreasing([1, 5, 3, 6, 7], [1, 6, 3, 3]));  // -1
 
console.log(makeArrayIncreasingTreeMap([1, 5, 3, 6, 7], [1, 3, 2, 4]));  // 1
console.log(makeArrayIncreasingTreeMap([1, 5, 3, 6, 7], [4, 3, 1]));  // -1
console.log(makeArrayIncreasingTreeMap([1, 5, 3, 6, 7], [1, 6, 3, 3]));  // -1
 
console.log(makeArrayIncreasingBruteForce([1, 5, 3, 6, 7], [1, 3, 2, 4]));  // 1
console.log(makeArrayIncreasingBruteForce([1, 5, 3, 6, 7], [4, 3, 1]));  // -1
console.log(makeArrayIncreasingBruteForce([1, 5, 3, 6, 7], [1, 6, 3, 3]));  // -1