LeetCode Entry

1920. Build Array from Permutation

06.05.2025 easy 2025 kotlin rust

n[n[i]]

1920. Build Array from Permutation easy blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/980

Problem TLDR

n[n[i]] #easy

Intuition

The follow up is more tricky: we have to store the result and preserver the initial values somehow, shift bits or do * and % operations.

Approach

  • do golf
  • do follow-up

Complexity

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

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

Code


// 3ms
    fun buildArray(n: IntArray) = n.map { n[it] }



// 2ms
    fun buildArray(n: IntArray): IntArray {
        for (i in n.indices) n[i] += (n[n[i]] and 0xFFFF) shl 16
        for (i in n.indices) n[i] = n[i] shr 16
        return n;
    }



// 1ms
    fun buildArray(n: IntArray) = IntArray(n.size) { n[n[i]] }



// 0ms
    pub fn build_array(mut n: Vec<i32>) -> Vec<i32> {
        for i in 0..n.len() { n[i] |= (n[n[i] as usize] & 0xFFFF) << 16 }
        for i in 0..n.len() { n[i] >>= 16 } n
    }



// 0ms
    pub fn build_array(n: Vec<i32>) -> Vec<i32> {
        n.iter().map(|&x| n[x as usize]).collect()
    }



// 0ms
    vector<int> buildArray(vector<int>& n) {
        vector<int> r(size(n));
        for (int i = 0; auto& x: n) r[i++] = n[x];
        return r;
    }