2501. Longest Square Streak in an Array

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Array、Hash Table、Binary Search、Dynamic Programming、Sorting
  • \(\color{blue}\textsf{Weekly Contest 323}\)

一、題目

You are given an integer array nums. A subsequence of nums is called a square streak if:

  • The length of the subsequence is at least 2, and
  • after sorting the subsequence, each element (except the first element) is the square of the previous number.
    Return the length of the longest square streak in nums, or return -1 if there is no square streak.
    A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

  • Input: nums = [4,3,6,16,8,2]
  • Output: 3
  • Explanation: Choose the subsequence [4,16,2]. After sorting it, it becomes [2,4,16].
  • 4 = 2 * 2.
  • 16 = 4 * 4.
    Therefore, [4,16,2] is a square streak.
    It can be shown that every subsequence of length 4 is not a square streak.

Example 2:

  • Input: nums = [2,3,5,6,7]
  • Output: -1
  • Explanation: There is no square streak in nums so return -1.

Constraints:

  • 2 <= nums.length <= 10^5
  • 2 <= nums[i] <= 10^5

二、分析

  • 先將 num 排序過後，遍歷所有的數字，並在遍歷的當下將數值存進 map 中，再找尋有沒有符合題意條件的數值在 map 中。
  • 令一個 dp(n)，代別 nums[n] 所具有的 longestSquareStreak，其中
    • if (map.count(sqrt(nums[i]))) dp[i] = dp[map[sqrt(nums[i])]] + 1
    • 需注意檢查 sqrt(nums[i]) * sqrt(nums[i] == nums[i]

三、解題

1. DP

  • Time complexity: \(O(n\log n)\)
  • Space complexity: \(O(n)\)
int longestSquareStreak(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    unordered_map<int,int> map;
    sort(nums.begin(), nums.end());
    int res = -1;
    for (int i = 0; i < nums.size(); i++) {
        int target = sqrt(nums[i]);
        if (target * target == nums[i]) {
            if (map.count(target)) {
                dp[i] = dp[map[target]] + 1;
                res = max(dp[i], res);
            }    
        }
        map[nums[i]] = i;
    }
    return res;
}

回目錄 Catalog