Longest common subsequence between sorted arrays

Array Hash Table Counting

81.3% acceptance

Mar 31, 2026

191

Given an array of integer arrays arrays where each arrays[i] is sorted in strictly increasing order, return an integer array representing the longest common subsequence among all the arrays. A subsequence is a sequence that can be derived from another sequence by deleting some elements (possibly none) without changing the order of the remaining elements.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn longest_common_subsequence(arrays: Vec<Vec<i32>>) -> Vec<i32> {
    let mut count = [0u8; 101];
    let n = arrays.len() as u8;
    for arr in &arrays {
      for &val in arr {
        count[val as usize] += 1;
      }
    }
    (1..=100).filter(|&i| count[i] == n).map(|i| i as i32).collect()
  }
}