Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1964.html
1964. Find the Longest Valid Obstacle Course at Each Position
Level
Hard
Description
You want to build some obstacle courses. You are given a 0-indexed integer array obstacles of length n, where obstacles[i] describes the height of the i-th obstacle.
For every index i between 0 and n - 1 (inclusive), find the length of the longest obstacle course in obstacles such that:
- You choose any number of obstacles between
0andiinclusive. - You must include the
i-thobstacle in the course. - You must put the chosen obstacles in the same order as they appear in
obstacles. - Every obstacle (except the first) is taller than or the same height as the obstacle immediately before it.
Return an array ans of length n, where ans[i] is the length of the longest obstacle course for index i as described above.
Example 1:
Input: obstacles = [1,2,3,2]
Output: [1,2,3,3]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [1], [1] has length 1.
- i = 1: [1,2], [1,2] has length 2.
- i = 2: [1,2,3], [1,2,3] has length 3.
- i = 3: [1,2,3,2], [1,2,2] has length 3.
Example 2:
Input: obstacles = [2,2,1]
Output: [1,2,1]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [2], [2] has length 1.
- i = 1: [2,2], [2,2] has length 2.
- i = 2: [2,2,1], [1] has length 1.
Example 3:
Input: obstacles = [3,1,5,6,4,2]
Output: [1,1,2,3,2,2]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [3], [3] has length 1.
- i = 1: [3,1], [1] has length 1.
- i = 2: [3,1,5], [3,5] has length 2. [1,5] is also valid.
- i = 3: [3,1,5,6], [3,5,6] has length 3. [1,5,6] is also valid.
- i = 4: [3,1,5,6,4], [3,4] has length 2. [1,4] is also valid.
- i = 5: [3,1,5,6,4,2], [1,2] has length 2.
Constraints:
n == obstacles.length1 <= n <= 10^51 <= obstacles[i] <= 10^7
Solution
For each element in obstacles, find the longest increasing subsequence that ends with the element. Use a greedy approach with binary search to do this.
-
class Solution { public int[] longestObstacleCourseAtEachPosition(int[] obstacles) { int length = obstacles.length; int[] longest = new int[length]; longest[0] = 1; int len = 1; int[] d = new int[length + 1]; d[len] = obstacles[0]; for (int i = 1; i < length; ++i) { if (obstacles[i] >= d[len]) { d[++len] = obstacles[i]; longest[i] = len; } else { int l = 1, r = len, pos = 0; while (l <= r) { int mid = (l + r) >> 1; if (d[mid] <= obstacles[i]) { pos = mid; l = mid + 1; } else { r = mid - 1; } } d[pos + 1] = obstacles[i]; longest[i] = pos + 1; } } return longest; } } ############ class Solution { public int lengthOfLIS(int[] nums) { TreeSet<Integer> ts = new TreeSet(); for (int v : nums) { ts.add(v); } int idx = 1; Map<Integer, Integer> m = new HashMap<>(); for (int v : ts) { m.put(v, idx++); } BinaryIndexedTree tree = new BinaryIndexedTree(m.size()); int ans = 1; for (int v : nums) { int x = m.get(v); int t = tree.query(x - 1) + 1; ans = Math.max(ans, t); tree.update(x, t); } return ans; } } class BinaryIndexedTree { private int n; private int[] c; public BinaryIndexedTree(int n) { this.n = n; c = new int[n + 1]; } public void update(int x, int val) { while (x <= n) { c[x] = Math.max(c[x], val); x += lowbit(x); } } public int query(int x) { int s = 0; while (x > 0) { s = Math.max(s, c[x]); x -= lowbit(x); } return s; } public static int lowbit(int x) { return x & -x; } } -
// OJ: https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/ // Time: O(NlogN) // Space: O(N) class Solution { public: vector<int> longestObstacleCourseAtEachPosition(vector<int>& A) { vector<int> ans, lis; for (int n : A) { int i = upper_bound(begin(lis), end(lis), n) - begin(lis); if (i == lis.size()) lis.push_back(n); else lis[i] = n; ans.push_back(i + 1); } return ans; } }; -
class BinaryIndexedTree: def __init__(self, n): self.n = n self.c = [0] * (n + 1) @staticmethod def lowbit(x): return x & -x def update(self, x, val): while x <= self.n: self.c[x] = max(self.c[x], val) x += BinaryIndexedTree.lowbit(x) def query(self, x): s = 0 while x > 0: s = max(s, self.c[x]) x -= BinaryIndexedTree.lowbit(x) return s class Solution: def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]: s = sorted(set(obstacles)) m = {v: i for i, v in enumerate(s, 1)} tree = BinaryIndexedTree(len(m)) ans = [] for v in obstacles: x = m[v] ans.append(1 + tree.query(x)) tree.update(x, ans[-1]) return ans ############ # 1964. Find the Longest Valid Obstacle Course at Each Position # https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/ class Solution: def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]: sl = [] res = [] for obs in obstacles: if len(sl) == 0 or sl[-1] <= obs: sl.append(obs) res.append(len(sl)) else: index = bisect.bisect(sl, obs) sl[index] = obs res.append(index + 1) return res -
type BinaryIndexedTree struct { n int c []int } func newBinaryIndexedTree(n int) *BinaryIndexedTree { c := make([]int, n+1) return &BinaryIndexedTree{n, c} } func (this *BinaryIndexedTree) lowbit(x int) int { return x & -x } func (this *BinaryIndexedTree) update(x, val int) { for x <= this.n { if this.c[x] < val { this.c[x] = val } x += this.lowbit(x) } } func (this *BinaryIndexedTree) query(x int) int { s := 0 for x > 0 { if s < this.c[x] { s = this.c[x] } x -= this.lowbit(x) } return s } func longestObstacleCourseAtEachPosition(obstacles []int) []int { s := make(map[int]bool) for _, v := range obstacles { s[v] = true } var t []int for v, _ := range s { t = append(t, v) } sort.Ints(t) m := make(map[int]int) for i, v := range t { m[v] = i + 1 } n := len(obstacles) ans := make([]int, n) tree := newBinaryIndexedTree(len(m)) for i, v := range obstacles { x := m[v] ans[i] = 1 + tree.query(x) tree.update(x, ans[i]) } return ans } -
class BinaryIndexedTree { private n: number; private c: number[]; constructor(n: number) { this.n = n; this.c = Array(n + 1).fill(0); } update(x: number, v: number): void { while (x <= this.n) { this.c[x] = Math.max(this.c[x], v); x += x & -x; } } query(x: number): number { let s = 0; while (x > 0) { s = Math.max(s, this.c[x]); x -= x & -x; } return s; } } function longestObstacleCourseAtEachPosition(obstacles: number[]): number[] { const nums: number[] = [...obstacles]; nums.sort((a, b) => a - b); const n: number = nums.length; const ans: number[] = []; const tree: BinaryIndexedTree = new BinaryIndexedTree(n); const search = (x: number): number => { let [l, r] = [0, n]; while (l < r) { const mid = (l + r) >> 1; if (nums[mid] >= x) { r = mid; } else { l = mid + 1; } } return l; }; for (let k = 0; k < n; ++k) { const i: number = search(obstacles[k]) + 1; ans[k] = tree.query(i) + 1; tree.update(i, ans[k]); } return ans; }