LeetCode Entry

2418. Sort the People

22.07.2024 easy 2024 kotlin rust

Sort one array by another

2418. Sort the People easy blog post substack youtube 2024-07-22_08-22_1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/678

Problem TLDR

Sort one array by another #easy

Intuition

We must use some extra memory for the relations between the arrays: it can be an indices array, or a zipped collection. Then sort it and recreate the answer.

Approach

  • Kotlin: withIndex, sortedByDescending.
  • Rust: using indices vec and recreating the result makes us use .clone(), so better use zip.

Complexity

  • Time complexity: \(O(nlogn)\)

  • Space complexity: \(O(n)\)

Code


    fun sortPeople(names: Array<String>, heights: IntArray) = names
        .withIndex()
        .sortedByDescending { heights[it.index] }
        .map { it.value }



    pub fn sort_people(names: Vec<String>, heights: Vec<i32>) -> Vec<String> {
        let mut zip: Vec<_> = names.into_iter().zip(heights.into_iter()).collect();
        zip.sort_unstable_by_key(|(n, h)| -h);
        zip.into_iter().map(|(n, h)| n).collect()
    }