1 day ago

Sarthak • 10

Hyderabad

Question: Athlete's Altitude Readings (Maximal Non-Decreasing Runs)

Problem Statement:

You are charting an athlete's altitude readings during a jog, represented by R. It is stored in an integer array A where the route naturally forms plateaus where altitude never decreases for a while and then drops.

You have to split array A into maximal non-decreasing runs (plateaus). For each plateau, add the (last - first) value of that run to a total. Your task is to find and return an integer value representing the sum of all maximal non-decreasing runs of (last_value - first_value).

Note: A "run" is a maximal segment you can't extend without breaking the non-decreasing property; i.e., within a run a[i] <= a[i+1], and the next element after the run is smaller (or the array ends).

Input Specification:

• input1: An integer value R, representing the number of readings.
• input2: An integer array A, representing the altitude readings.

Output Specification:

• Return an integer value representing the sum of all maximal non-decreasing runs of (last_value - first_value)

Example 1:

Input:

input1 : 7

input2 : {2, 2, 5, 4, 4, 6, 1}

Output:

5

Explanation:

Here, R = 7 and A = {2, 2, 5, 4, 4, 6, 1}. Plateaus (maximal non-decreasing runs) are as below:

• [2, 2, 5] 5 - 2 = 3
• [4, 4, 6] 6 - 4 = 2
• [1] 1 - 1 = 0

Total = 3 + 2 + 0 = 5. Hence, 5 is returned as the output.

9 hours ago

admin 1.9k

Hyderabad

Problem1 Solution

Athlete's Altitude Readings Solution

Topics Involved / Prerequisites

• Array Traversal
• Mathematical Accumulation

Overview

The problem requires us to find "maximal non-decreasing runs" and sum the difference between the last and first elements of each run.

While you could manually track the start and end indices of every single plateau, there is a much simpler mathematical trick. For any non-decreasing sequence like [a, b, c], the difference between the last and first element (c - a) is exactly mathematically equal to the sum of the adjacent differences: (b - a) + (c - b).

Because of this, we only need to look at adjacent pairs. If the current altitude is greater than or equal to the previous altitude, we simply add their difference to our total. If it drops, we do nothing and effectively "start a new run" on the next step.

Approach

1. Initialize Variables

We need a total_sum variable initialized to 0 to keep track of our accumulated altitude gains.

2. Single Pass Traversal

We loop through the array starting from the second element (index 1) up to the end (index R - 1).

• At each step, we compare the current element A[i] with the previous element A[i-1].
• If A[i] >= A[i-1], it means we are walking along a non-decreasing plateau. We add A[i] - A[i-1] to our total_sum.
• If A[i] < A[i-1], the altitude dropped, breaking the plateau. We ignore it and continue, which naturally starts the logic over for the next plateau.

Code Implementation (Python)

def calculate_altitude_sum(input1, input2):
    # input1 corresponds to the length of the list (input2)
    if input1 <= 1:
        return 0
    
    total_sum = 0
    
    # Iterate from the second element to the end
    for i in range(1, input1):
        # Only add the difference if the current altitude is higher or equal
        if input2[i] >= input2[i - 1]:
            total_sum += (input2[i] - input2[i - 1])
            
    return total_sum

Time and Space Complexity

• Time Complexity: O(N) — We traverse the array of R readings exactly once, making a single constant-time comparison at each step.
• Space Complexity: O(1) — We only use a single integer variable to store the sum, requiring no extra memory scaling.