C++ One-Dimensional Array Problems: Sum, Avg, Max-Min, Sorting & Reversal

7
0

One-Dimensional Arrays: Problem Solving

Array problems become easier when each requirement is converted into a repeatable traversal pattern. Some problems need an accumulated result, some maintain the best value found so far, some compare neighboring elements, and others use two indexes moving from opposite ends. These patterns form the foundation for solving more advanced array problems.

Problem 1: Find the Sum and Average

Given an integer array, the first task is to calculate the sum of all its elements. The average is then calculated by dividing that sum by the number of elements.

For the array {10, 20, 30, 40}:

  • The sum is 10 + 20 + 30 + 40 = 100.

  • The number of elements is 4.

  • The average is 100 / 4 = 25.

Using an Accumulator

An accumulator is a variable that stores a result while the array is being traversed. For summation, it begins at 0 because adding zero does not affect the result. Each array element is then added to the current sum.

  • Initially, sum = 0.

  • After processing 10, sum = 10.

  • After processing 20, sum = 30.

  • After processing 30, sum = 60.

  • After processing 40, sum = 100.

The statement sum += arr[i] is a shorter form of sum = sum + arr[i]. Once every element has been processed, the accumulator contains the required total.

Handling Integer Division

The average can contain a fractional part, so its return type should be double. Dividing one integer by another performs integer division before the result is assigned. For example, integer division evaluates 5 / 2 as 2, not 2.5.

At least one operand must therefore be converted to double before division. The expression static_cast<double>(sum) / n preserves the fractional part.

#include <iostream>
using namespace std;
int sumOfArray(int arr[], int n) {
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
return sum;
}
double averageOfArray(int arr[], int n) {
int sum = sumOfArray(arr, n);
return static_cast(sum) / n;
}
int main() {
int arr[] = {10, 20, 30, 40};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Sum: " << sumOfArray(arr, n) << '\n';
cout << "Average: " << averageOfArray(arr, n) << '\n';
return 0;
}

The sum function performs one traversal, so its time complexity is O(n) and its auxiliary space complexity is O(1). The average function reuses sumOfArray instead of repeating the traversal logic. It assumes that n is greater than zero because an empty array has no arithmetic mean.

Problem 2: Find the Maximum and Minimum

Given a non-empty array, the task is to return its largest and smallest elements. For {4, 9, 2, 7}, the maximum is 9 and the minimum is 2.

The Current Champion Method

The first element can be treated as the current best answer because the array is guaranteed to be non-empty. The remaining elements are then compared with this current champion.

To find the maximum in {4, 9, 2, 7}:

  • Start with maximum = 4.

  • 9 is greater than 4, so the maximum becomes 9.

  • 2 is not greater than 9, so no update is needed.

  • 7 is not greater than 9, so the final maximum is 9.

The minimum follows the same pattern with the comparison reversed:

  • Start with minimum = 4.

  • 9 is not smaller than 4.

  • 2 is smaller than 4, so the minimum becomes 2.

  • 7 is not smaller than 2, so the final minimum is 2.

Traversal begins at index 1 because index 0 has already been used to initialize the answer. Initializing with the first element is more reliable than starting with an arbitrary value such as 0. If every array element were negative, using zero as the initial maximum would produce an incorrect result.

#include <iostream>
using namespace std;
int maximumElement(int arr[], int n) {
int maximum = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > maximum) {
maximum = arr[i];
}
}
return maximum;
}
int minimumElement(int arr[], int n) {
int minimum = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] < minimum) {
minimum = arr[i];
}
}
return minimum;
}
int main() {
int arr[] = {4, 9, 2, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum: " << maximumElement(arr, n) << '\n';
cout << "Minimum: " << minimumElement(arr, n) << '\n';
return 0;
}

Each function examines every relevant element once. The time complexity is O(n), while the auxiliary space complexity is O(1). A single-element array also works: its only value is both the maximum and the minimum, and the loop executes zero times.

Problem 3: Check Whether an Array Is Sorted

An array is sorted in non-decreasing order when every element is greater than or equal to the element immediately before it. Equal neighboring values are allowed, which is why the term is non-decreasing rather than strictly increasing.

  • {1, 2, 2, 5, 8} is sorted because it never decreases while moving from left to right.

  • {1, 4, 3, 7} is not sorted because 3 is smaller than the preceding value 4.

Comparing Adjacent Elements

The element at index 0 has no element to its left, so comparison begins at index 1. At every index i, compare arr[i] with arr[i - 1].

For {1, 2, 2, 5, 8}, the comparisons are:

  • 2 >= 1

  • 2 >= 2

  • 5 >= 2

  • 8 >= 5

Every comparison is valid, so the function returns true. The equality in 2 >= 2 is valid and must not be treated as a violation.

For {1, 4, 3, 7}, 4 >= 1 is valid, but 3 >= 4 is false. Equivalently, arr[i] < arr[i - 1] identifies a decrease. Once one violation is found, the complete array cannot be sorted, so the function can return false immediately.

#include <iostream>
using namespace std;
bool isArraySorted(int arr[], int n) {
for (int i = 1; i < n; i++) {
if (arr[i] < arr[i - 1]) {
return false;
}
}
return true;
}
int main() {
int first[] = {1, 2, 2, 5, 8};
int second[] = {1, 4, 3, 7};
cout << isArraySorted(first, 5) << '\n';
cout << isArraySorted(second, 4) << '\n';
return 0;
}

By default, C++ prints true as 1 and false as 0, so this program prints 1 followed by 0. If no violating pair is found, the loop finishes and the final return true; executes.

The worst-case time complexity is O(n), and the auxiliary space complexity is O(1). Because of the early return, an unsorted array may require fewer comparisons. For example, if the first adjacent pair is decreasing, the function finishes after a single comparison.

Problem 4: Reverse an Array

Reversing an array means placing its elements in the opposite order. The array {10, 20, 30, 40, 50} becomes {50, 40, 30, 20, 10}.

The requirement to reverse the array in place is important. It means that the original array must be updated without creating another array proportional to the input size. A useful problem-solving process is to begin with the most direct method and then improve it to satisfy this constraint.

Brute-Force Approach Using a Duplicate Array

The direct approach creates an auxiliary array of the same size. Traverse the original array from its last index to its first index and place each value into the auxiliary array from left to right.

For {10, 20, 30, 40, 50}:

  • Read 50 from index 4 and place it at duplicate index 0.

  • Read 40 from index 3 and place it at duplicate index 1.

  • Continue until 10 is placed at duplicate index 4.

  • Copy the completed duplicate array back into the original array.

#include <iostream>
using namespace std;
void reverseBruteForce(int arr[], int n) {
int duplicate[n];
int j = 0;
for (int i = n - 1; i >= 0; i--) {
duplicate[j] = arr[i];
j++;
}
for (int i = 0; i < n; i++) {
arr[i] = duplicate[i];
}
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
reverseBruteForce(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << ' ';
}
return 0;
}

This method uses two traversals: one to build the reversed copy and another to copy it back. Its total time complexity is still O(n) because O(n) + O(n) simplifies to O(n). However, its auxiliary space complexity is O(n), so it does not satisfy the in-place requirement.

Optimal In-Place Approach Using Two Pointers

Observe how positions change during reversal. The first and last elements exchange places, then the second and second-last elements exchange places, and the pattern continues toward the center. This leads to the two-pointer technique.

  • Set left = 0 to point to the first element.

  • Set right = n - 1 to point to the last element.

  • Swap arr[left] and arr[right].

  • Move left one position forward and right one position backward.

  • Continue while left < right.

Dry Run for an Odd Number of Elements

Consider {10, 20, 30, 40, 50}:

  • Swap 10 and 50 to get {50, 20, 30, 40, 10}.

  • Move inward and swap 20 and 40 to get {50, 40, 30, 20, 10}.

  • Both pointers now meet at 30. The middle element is already in its correct position, so no further swap is needed.

Dry Run for an Even Number of Elements

Consider {1, 2, 3, 4, 5, 6}:

  • Swap 1 and 6 to get {6, 2, 3, 4, 5, 1}.

  • Swap 2 and 5 to get {6, 5, 3, 4, 2, 1}.

  • Swap 3 and 4 to get {6, 5, 4, 3, 2, 1}.

  • The pointers then cross, so reversal is complete.

For an odd-length array, the pointers eventually meet. For an even-length array, they cross. Both cases are handled by continuing only while left < right. Equivalently, the process stops when left >= right.

#include <iostream>
#include <utility>
using namespace std;
void reverseInPlace(int arr[], int n) {
int left = 0;
int right = n - 1;
while (left < right) {
swap(arr[left], arr[right]);
left++;
right--;
}
}
int main() {
int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]);
reverseInPlace(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << ' ';
}
return 0;
}

The loop performs approximately n / 2 swaps. Its time complexity is O(n), and it uses only the two pointer variables, giving it O(1) auxiliary space. The original array is modified directly, so the function does not need to return it.

The pointer updates can also be placed inside the swap expression as swap(arr[left++], arr[right--]). Postfix increment and decrement use the current indexes for the swap and update them afterward. Keeping the updates on separate lines is usually clearer and makes the movement of both pointers explicit.

Comparing the Problem-Solving Patterns

  • Accumulation: Start with a neutral value and combine every element into it, as in array summation.

  • Current champion: Keep the best candidate found so far and replace it whenever a better value appears, as in minimum and maximum problems.

  • Adjacent comparison: Compare each element with its predecessor to validate an ordering property.

  • Early termination: Return immediately when a condition has already determined the answer, as in detecting an unsorted pair.

  • Brute force followed by optimization: Begin with a correct direct solution, identify the unnecessary resource, and remove it.

  • Two pointers: Place indexes at opposite ends and move them inward when the problem involves paired positions.

Summary

These problems demonstrate that array problem solving is largely about recognizing how information should move during traversal. Sum and average use an accumulator, minimum and maximum maintain a current champion, sorted-order checking compares neighboring elements with an early return, and reversal pairs elements from opposite ends. Once these patterns become familiar, many array questions can be reduced to a small and precise loop with clear boundaries.

C++

Read Similar Blogs

C++

Recursion Problem Solving II: Array Traversal, Sorting Check and Reversal

Recursion Problem Solving - II Arrays are naturally suited to recursive processing because an array range can be divided into a current element and a smaller remaining range. A recursive function c...

9
C++

Recursion Problem Solving I: Power, Digit Sum and Number Reversal

Recursion Problem Solving - I Recursive problem solving begins by defining exactly what a function should return. The current problem is then expressed in terms of the same function applied to a sm...

8
C++

Recursion in C++ Explained: Base Cases, Call Stack and Recursive Functions

Recursion Foundation and Call Flow Recursion is a problem-solving technique in which a function calls itself with a smaller version of the original problem. Each call handles one part of the work a...

9
Comments0