Length of the longest increasing path

Array Binary Search Sorting

19.2% acceptance

Feb 25, 2026

102

You are given a 2D array of integers coordinates of length n and an integer k, where 0 <= k < n. coordinates[i] = [xi, yi] indicates the point (xi, yi) in a 2D plane. An increasing path of length m is defined as a list of points (x1,y1),(x2,y2),...,(xm,ym) such that xi < xi+1 and yi < yi+1 for all 1 <= i < m. Return the maximum length of an increasing path that contains coordinates[k].

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_path_length(coordinates: Vec<Vec<i32>>, k: i32) -> i32 {
    let k = k as usize;
    let kx = coordinates[k][0];
    let ky = coordinates[k][1];
    
    // Points that can be BEFORE k in increasing path: x < kx && y < ky
    // Points that can be AFTER k in increasing path: x > kx && y > ky
    // Longest increasing subsequence of points ordered by x (then by -y for same x to avoid duplicates)
    
    let lis_len = |mut pts: Vec<(i32, i32)>| -> i32 {
      // Sort by x asc, then y desc (so same x won't chain)
      pts.sort_by(|a, b| a.0.cmp(&b.0).then(b.1.cmp(&a.1)));
      // LIS on y values
      let mut tails: Vec<i32> = Vec::new();
      for (_, y) in pts {
        let pos = tails.partition_point(|&t| t < y);
        if pos == tails.len() {
          tails.push(y);
        } else {
          tails[pos] = y;
        }
      }
      tails.len() as i32
    };
    
    let before: Vec<(i32, i32)> = coordinates.iter()
      .map(|c| (c[0], c[1]))
      .filter(|&(x, y)| x < kx && y < ky)
      .collect();
    
    let after: Vec<(i32, i32)> = coordinates.iter()
      .map(|c| (c[0], c[1]))
      .filter(|&(x, y)| x > kx && y > ky)
      .collect();
    
    lis_len(before) + 1 + lis_len(after)
  }
}