Array Transformation - Practice Coding Problems

Array Transformation - Problem

Array Simulation Easy

Given an initial array arr, every day you produce a new array using the array of the previous day.

On the i-th day, you do the following operations on the array of day i-1 to produce the array of day i:

If an element is smaller than both its left neighbor and its right neighbor, then this element is incremented.
If an element is bigger than both its left neighbor and its right neighbor, then this element is decremented.
The first and last elements never change.

After some days, the array does not change. Return that final array.

Input & Output

Example 1 — Basic Transformation

$ Input: arr = [6,2,3,4]

› Output: [6,4,4,4]

💡 Note: Day 1: 2<6 and 2<3, so 2→3. Array becomes [6,3,3,4]. Day 2: 3<6 and 3<3 (false), but middle 3<4, so 3→4. Continue until stable at [6,4,4,4].

Example 2 — Peak Reduction

$ Input: arr = [1,6,3,4,1]

› Output: [1,4,4,4,1]

💡 Note: 6>1 and 6>3, so 6→5. Then 5>4 and 5>4, so 5→4. Process continues until all peaks are flattened to [1,4,4,4,1].

Example 3 — Already Stable

$ Input: arr = [2,1,1,1]

› Output: [2,1,1,1]

💡 Note: Middle elements 1 are not smaller than both neighbors (1≮1), so no changes occur. Array is already stable.

Constraints

1 ≤ arr.length ≤ 100
1 ≤ arr[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Initial State

Array with peaks and valleys: [6,2,3,4]

Transform

Apply increment/decrement rules to middle elements

Final State

Stable equilibrium reached: [6,4,4,4]

Key Takeaway

🎯 Key Insight: Elements naturally converge to equilibrium - valleys fill up, peaks flatten down

Asked in

G Google 15 a Amazon 12 Apple 8 f Facebook 6

The key insight is that elements will gradually converge to equilibrium with their neighbors. Best approach is day-by-day simulation - simple and intuitive. Time: O(k × n), Space: O(n) for copying arrays or O(1) for in-place updates.

Common Approaches

Approach	Time	Space	Notes
✓ In-Place Simulation	O(k × n)	O(1)	Optimize space by modifying array in-place with careful indexing
Day-by-Day Simulation	O(k × n)	O(n)	Simulate the transformation process day by day until no changes occur

In-Place Simulation — Algorithm Steps

Step 1: Identify all elements that need to change in current iteration
Step 2: Apply all changes simultaneously to avoid interference
Step 3: Repeat until no elements need changes

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan Array

Find all elements that need to change

Batch Update

Apply all changes at once to avoid conflicts

Check Completion

Stop when no changes are needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int index;
    int value;
} Change;

int* solution(int* arr, int size, int* returnSize) {
    *returnSize = size;
    if (size <= 2) {
        int* result = (int*)malloc(size * sizeof(int));
        memcpy(result, arr, size * sizeof(int));
        return result;
    }
    
    int* result = (int*)malloc(size * sizeof(int));
    memcpy(result, arr, size * sizeof(int));
    
    while (true) {
        Change changes[100];
        int changeCount = 0;
        
        // Identify all changes needed
        for (int i = 1; i < size - 1; i++) {
            int left = result[i-1], curr = result[i], right = result[i+1];
            if (curr < left && curr < right) {
                changes[changeCount++] = (Change){i, curr + 1};
            } else if (curr > left && curr > right) {
                changes[changeCount++] = (Change){i, curr - 1};
            }
        }
        
        if (changeCount == 0) return result;
        
        // Apply all changes
        for (int i = 0; i < changeCount; i++) {
            result[changes[i].index] = changes[i].value;
        }
    }
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int arr[100];
    int size = 0;
    char* ptr = line + 1; // Skip '['
    
    while (*ptr && *ptr != ']') {
        if (*ptr == ',' || *ptr == ' ') {
            ptr++;
            continue;
        }
        arr[size++] = atoi(ptr);
        while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
    }
    
    int returnSize;
    int* result = solution(arr, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × n)

k days until convergence, each day processes n elements

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra space for tracking changes

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

In-Place Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler