Teaching Kids Programming – Number of Changing Directions

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) —