Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a list of integers nums, return the number of times that the list changes from positive-to-negative or negative-to-positive slope.
Constraints
n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 3, 9, 7, 5, 10, 12]
Output
2
Explanation
Change of direction happens at 9 (positive-to-negative slope), and then at 5 (negative-to-positive slope).Example 2
Input
nums = [1, 2, 3, 3, 2, 1]
Output
0
Explanation
The slope is 0 between [3, 3]. So there are no positive-to-negative or negative-to-positive changes in slope since 0 is neither positive nor negative.
Slope Changing Counting Algorithm
We need to keep updating the current slope which can be calculated as the difference between current number and previous number. And if next slope has a different sign – we increment the answer. The sign can be computed as the multiplication of the slope if being negative meaning the slope has changed.
1 2 3 4 5 6 7 8 9 10 11 12 13 | class Solution: def changingDirections(self, nums): n = len(nums) if not nums or n <= 2: return 0 ans = 0 slope = nums[1] - nums[0] for i in range(2, n): cur = nums[i] - nums[i - 1] if cur * slope < 0: ans += 1 slope = cur return ans |
class Solution: def changingDirections(self, nums): n = len(nums) if not nums or n <= 2: return 0 ans = 0 slope = nums[1] - nums[0] for i in range(2, n): cur = nums[i] - nums[i - 1] if cur * slope < 0: ans += 1 slope = cur return ans
Time complexity is O(N) where N is the numbers in the array – as we need to iterate once the array.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: The Pair Class Implementation in Java
Next Post: GoLang: Command Line Unique Tool (Read from Keyboard)