LeetCode Entry

2501. Longest Square Streak in an Array

28.10.2024 medium 2024 kotlin rust

Longest quadratic subset

2501. Longest Square Streak in an Array medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/783

Problem TLDR

Longest quadratic subset #medium #hashmap #math

Intuition

Let’s look at the problem:

    [4,3,6,16,8,2]
     *               2 or 8
       *             9
         *           36
           *         4 or 256
              *      64
                *    4

For each number n we want to know if any n^2 or sqrt(n) is present. We can use a HashMap to store that fact. Other interesting notes:

• in increasing order, we only care about one next number n^2
• the problem set is 10^5, the biggest n^2 = 316 * 316, we can search just 2..316 range

Approach

• let’s do a sorting + hashmap solution in Kotlin, and optimized solution in Rust
• careful with an int overflow

Complexity

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

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

Code

    fun longestSquareStreak(nums: IntArray): Int {
        val streak = mutableMapOf<Int, Int>()
        return nums.sorted().maxOf { n ->
            (1 + (streak[n] ?: 0)).also { streak[n * n] = it }
        }.takeIf { it > 1 } ?: -1
    }

    pub fn longest_square_streak(nums: Vec<i32>) -> i32 {
        let (mut set, mut vmax, mut max) = ([0; 316 * 316 + 1], 0, -1);
        for n in nums { let n = n as usize; if n < set.len() {
            set[n] = 1; vmax = vmax.max(n);
        }}
        for start in 2..317 { if set[start] > 0 {
            let (mut sq, mut streak) = (start * start, 1);
            while 0 < sq && sq <= vmax && set[sq] > 0 {
                streak += 1; sq = sq * sq; max = max.max(streak)
            }
        }}; max
    }

    int longestSquareStreak(vector<int>& nums) {
        int set[316 * 316 + 1] = {}, vmax = 0, res = -1;
        for (int n: nums) if (n <= 316 * 316) set[n] = 1, vmax = max(vmax, n);
        for (int start = 2; start < 317; ++start) if (set[start]) {
            long sq = start * start; int streak = 1;
            while (sq <= vmax && set[sq]) ++streak, sq *= sq, res = max(res, streak);
        }
        return res;
    }