aboutsummaryrefslogtreecommitdiff
path: root/longest_square_streak_arr.py
diff options
context:
space:
mode:
Diffstat (limited to 'longest_square_streak_arr.py')
-rw-r--r--longest_square_streak_arr.py36
1 files changed, 36 insertions, 0 deletions
diff --git a/longest_square_streak_arr.py b/longest_square_streak_arr.py
new file mode 100644
index 0000000..795bf33
--- /dev/null
+++ b/longest_square_streak_arr.py
@@ -0,0 +1,36 @@
+# 2501. Longest Square Streak in an Array
+from math import isqrt
+
+"""
+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 '-1' otherwise. 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.
+"""
+
+
+class Solution(object):
+ def longestSquareStreak(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ mp, ans = {}, -1
+ nums.sort()
+ for i in nums:
+ sqrt = isqrt(i)
+ if sqrt * sqrt == i and sqrt in mp:
+ mp[i] = mp[sqrt] + 1
+ ans = max(ans, mp[i])
+ else:
+ mp[i] = 1
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.longestSquareStreak(nums=[4, 3, 6, 16, 8, 2]))
+ print(obj.longestSquareStreak(nums=[2, 3, 5, 6, 7]))