Find the Longest Valid Obstacle Course at Each Position

// Accepted solution for LeetCode #1964: Find the Longest Valid Obstacle Course at Each Position
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 v) {
        while (x <= n) {
            c[x] = Math.max(c[x], v);
            x += x & -x;
        }
    }

    public int query(int x) {
        int s = 0;
        while (x > 0) {
            s = Math.max(s, c[x]);
            x -= x & -x;
        }
        return s;
    }
}

class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int[] nums = obstacles.clone();
        Arrays.sort(nums);
        int n = nums.length;
        int[] ans = new int[n];
        BinaryIndexedTree tree = new BinaryIndexedTree(n);
        for (int k = 0; k < n; ++k) {
            int x = obstacles[k];
            int i = Arrays.binarySearch(nums, x) + 1;
            ans[k] = tree.query(i) + 1;
            tree.update(i, ans[k]);
        }
        return ans;
    }
}

// Accepted solution for LeetCode #1964: Find the Longest Valid Obstacle Course at Each Position
type BinaryIndexedTree struct {
	n int
	c []int
}

func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
	return &BinaryIndexedTree{n, make([]int, n+1)}
}

func (bit *BinaryIndexedTree) update(x, v int) {
	for x <= bit.n {
		bit.c[x] = max(bit.c[x], v)
		x += x & -x
	}
}

func (bit *BinaryIndexedTree) query(x int) (s int) {
	for x > 0 {
		s = max(s, bit.c[x])
		x -= x & -x
	}
	return
}

func longestObstacleCourseAtEachPosition(obstacles []int) (ans []int) {
	nums := slices.Clone(obstacles)
	sort.Ints(nums)
	n := len(nums)
	tree := NewBinaryIndexedTree(n)
	for k, x := range obstacles {
		i := sort.SearchInts(nums, x) + 1
		ans = append(ans, tree.query(i)+1)
		tree.update(i, ans[k])
	}
	return
}

# Accepted solution for LeetCode #1964: Find the Longest Valid Obstacle Course at Each Position
class BinaryIndexedTree:
    __slots__ = ["n", "c"]

    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, v: int):
        while x <= self.n:
            self.c[x] = max(self.c[x], v)
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x:
            s = max(s, self.c[x])
            x -= x & -x
        return s


class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        nums = sorted(set(obstacles))
        n = len(nums)
        tree = BinaryIndexedTree(n)
        ans = []
        for x in obstacles:
            i = bisect_left(nums, x) + 1
            ans.append(tree.query(i) + 1)
            tree.update(i, ans[-1])
        return ans

// Accepted solution for LeetCode #1964: Find the Longest Valid Obstacle Course at Each Position
/**
 * [1964] Find the Longest Valid Obstacle Course at Each Position
 *
 * 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 0 and i inclusive.
 * 	You must include the i^th obstacle 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: [<u>1</u>], [1] has length 1.
 * - i = 1: [<u>1</u>,<u>2</u>], [1,2] has length 2.
 * - i = 2: [<u>1</u>,<u>2</u>,<u>3</u>], [1,2,3] has length 3.
 * - i = 3: [<u>1</u>,<u>2</u>,3,<u>2</u>], [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: [<u>2</u>], [2] has length 1.
 * - i = 1: [<u>2</u>,<u>2</u>], [2,2] has length 2.
 * - i = 2: [2,2,<u>1</u>], [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: [<u>3</u>], [3] has length 1.
 * - i = 1: [3,<u>1</u>], [1] has length 1.
 * - i = 2: [<u>3</u>,1,<u>5</u>], [3,5] has length 2. [1,5] is also valid.
 * - i = 3: [<u>3</u>,1,<u>5</u>,<u>6</u>], [3,5,6] has length 3. [1,5,6] is also valid.
 * - i = 4: [<u>3</u>,1,5,6,<u>4</u>], [3,4] has length 2. [1,4] is also valid.
 * - i = 5: [3,<u>1</u>,5,6,4,<u>2</u>], [1,2] has length 2.
 *
 *  
 * Constraints:
 *
 * 	n == obstacles.length
 * 	1 <= n <= 10^5
 * 	1 <= obstacles[i] <= 10^7
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/
// discuss: https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn longest_obstacle_course_at_each_position(obstacles: Vec<i32>) -> Vec<i32> {
        vec![]
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_1964_example_1() {
        let obstacles = vec![1, 2, 3, 2];

        let result = vec![1, 2, 3, 3];

        assert_eq!(
            Solution::longest_obstacle_course_at_each_position(obstacles),
            result
        );
    }

    #[test]
    #[ignore]
    fn test_1964_example_2() {
        let obstacles = vec![2, 2, 1];

        let result = vec![1, 2, 1];

        assert_eq!(
            Solution::longest_obstacle_course_at_each_position(obstacles),
            result
        );
    }

    #[test]
    #[ignore]
    fn test_1964_example_3() {
        let obstacles = vec![3, 1, 5, 6, 4, 2];

        let result = vec![1, 1, 2, 3, 2, 2];

        assert_eq!(
            Solution::longest_obstacle_course_at_each_position(obstacles),
            result
        );
    }
}

// Accepted solution for LeetCode #1964: Find the Longest Valid Obstacle Course at Each Position
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;
}