Leetcode 2501: Longest Square Streak in an Array
You are given an integer array nums. A subsequence of nums is called a square streak if its length is at least 2, and after sorting the subsequence, each element (except the first one) is the square of the previous number. Return the length of the longest square streak in nums, or -1 if no square streak exists.
Problem
Approach
Steps
Complexity
Input: You are given an array nums, where each element is a positive integer.
Example: Input: nums = [9,3,16,2,4,81]
Constraints:
• 2 <= nums.length <= 10^5
• 2 <= nums[i] <= 10^5
Output: Return the length of the longest subsequence that forms a square streak. If no such subsequence exists, return -1.
Example: Output: 3
Constraints:
• If no subsequence satisfies the conditions, return -1.
Goal: Find the longest subsequence where each element (except the first) is the square of the previous one.
Steps:
• 1. Sort the array to easily check the relationship between elements.
• 2. Use dynamic programming to store the longest square streak for each element.
• 3. Iterate over the array, check for the condition where an element is the square of the previous one.
• 4. Keep track of the maximum length of any such subsequence.
Goal: The input array nums follows the given size and element constraints.
Steps:
• The length of nums is between 2 and 10^5.
• Each element in nums is between 2 and 10^5.
Assumptions:
• There are no duplicate numbers in the array.
• The array contains at least two elements.
• Input: Input: nums = [9, 3, 16, 2, 4, 81]
• Explanation: In this example, the subsequence [4, 16, 81] is a square streak. After sorting, it becomes [4, 16, 81], where 16 = 4 * 4 and 81 = 16 * 16. Therefore, the longest square streak has a length of 3.
• Input: Input: nums = [5, 2, 3, 7]
• Explanation: There is no subsequence that satisfies the square streak condition, so the output is -1.
Approach: The approach involves sorting the array and using dynamic programming to find the longest subsequence where each number is the square of the previous one.
Observations:
• Sorting the array helps to easily identify potential square relationships between numbers.
• Using dynamic programming ensures that we can efficiently calculate the longest square streak by considering each element as part of a subsequence.
Steps:
• 1. Sort the array nums to ensure elements are checked in ascending order.
• 2. Initialize a dp array to store the longest square streak ending at each element.
• 3. For each element in nums, check if the square of the element exists in the array. If it does, update the dp array for that element.
• 4. Track the longest streak as you go through the array.
• 5. Return the longest square streak, or -1 if no streak exists.
Empty Inputs:
• The array will always have at least two elements, so this case is not applicable.
Large Inputs:
• Ensure the solution handles large inputs efficiently, given the constraint of up to 10^5 elements.
Special Values:
• Handle arrays where no subsequences form a square streak.
Constraints:
• The solution must work efficiently within the given constraints.
int longestSquareStreak(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<int> dp(n, 1);
int mx = 1;
for(int i= 0; i < n; i++) {
long long tmp = (long long) nums[i] * nums[i];
if(tmp > INT_MAX) break;
auto it = lower_bound(nums.begin(), nums.end(), tmp);
if(it == nums.end()) break;
int pos = it - nums.begin();
while(pos < n && nums[i] * nums[i] == nums[pos]) {
dp[pos] = max(dp[pos], 1 + dp[i]);
mx = max(mx, dp[pos]);
pos++;
}
}
return mx == 1? -1: mx;
}
1 : Function Definition
int longestSquareStreak(vector<int>& nums) {
Defines the function `longestSquareStreak` which takes a vector `nums` and returns an integer representing the longest streak of numbers whose squares also exist in the list.
2 : Variable Initialization
int n = nums.size();
Initializes the variable `n` to the size of the vector `nums`.
3 : Sorting
sort(nums.begin(), nums.end());
Sorts the vector `nums` in ascending order.
4 : Dynamic Programming Initialization
vector<int> dp(n, 1);
Creates a vector `dp` initialized to 1, which will store the longest streak of numbers for each element.
5 : Variable Initialization
int mx = 1;
Initializes the variable `mx` to 1 to store the maximum streak length.
6 : Looping
for(int i= 0; i < n; i++) {
Starts a loop to iterate over each element `i` in the sorted vector `nums`.
7 : Mathematical Operations
long long tmp = (long long) nums[i] * nums[i];
Calculates the square of the current element `nums[i]` and stores it in the variable `tmp`.
8 : Conditionals
if(tmp > INT_MAX) break;
Checks if the square of the number exceeds the maximum possible integer value, in which case the loop breaks.
9 : Binary Search
auto it = lower_bound(nums.begin(), nums.end(), tmp);
Uses binary search (`lower_bound`) to find the position of `tmp` in the sorted vector `nums`.
10 : Conditionals
if(it == nums.end()) break;
Checks if the position returned by `lower_bound` is at the end of the vector, meaning `tmp` is not found.
11 : Pointer Operations
int pos = it - nums.begin();
Calculates the index of the found element `tmp` in the vector `nums`.
12 : Looping
while(pos < n && nums[i] * nums[i] == nums[pos]) {
Starts a nested loop to check for consecutive elements in `nums` that match the square of the current element.
13 : Dynamic Programming Update
dp[pos] = max(dp[pos], 1 + dp[i]);
Updates the value of `dp[pos]` to be the maximum of its current value or the streak length of `dp[i]` plus 1.
14 : Result Calculation
mx = max(mx, dp[pos]);
Updates the maximum streak length `mx` by comparing it with the current streak length `dp[pos]`.
15 : Pointer Operations
pos++;
Increments the position `pos` to check the next element in the streak.
16 : Return Statement
return mx == 1? -1: mx;
Returns the result: if no streaks were found (`mx == 1`), returns -1; otherwise, returns the length of the longest streak.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The sorting step takes O(n log n), and the dynamic programming step requires O(n) time, resulting in an overall time complexity of O(n log n).
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the dp array used for storing the longest square streaks for each element.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus