LeetCode Entry

396. Rotate Function

01.05.2026 medium 2026 kotlin rust

Max rolling hash

396. Rotate Function medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1345

Problem TLDR

Max rolling hash

Intuition

    // 0a 1b 2c 3d
    //    0b 1c 2d 3a
    // +3 -1 -1 -1
    // 3a-(b+c+d)
    //       0c 1d 2a 3b
    //    +3 -1 -1 -1

Reuse the previous hash to make a new. 0a1b2c3d converts to 0b1c2d3a=prev+3a-(b+c+d)=prev+3a-(sum-a)=prev+size*a-sum

Approach

• Rust has a nice way to (0..).zip(&n)

Complexity

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

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

Code

    fun maxRotateFunction(n: IntArray) = n.run {
        val s = sum(); var a = indices.sumOf { it*n[it] }
        maxOf { x -> a.also { a += size*x - s }}
    }

    pub fn max_rotate_function(n: Vec<i32>) -> i32 {
        let (s, mut f) = (0..).zip(&n).fold((0,0), |(s,f),(i,x)|(s+x,f+i*x));
        n.iter().map(|x| (f, f+=n.len()as i32*x-s).0).max().unwrap()
    }