Chapter 9 Intermediate 59 Questions

Practice Questions — Arrays and Multidimensional Arrays

← Back to Notes
11 Easy
14 Medium
10 Hard

Topic-Specific Questions

Question 1
Easy
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    cout << arr[0] << " " << arr[4] << endl;
    return 0;
}
Arrays are 0-indexed. arr[0] is first, arr[4] is last.
10 50
Question 2
Easy
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[5] = {1, 2};
    for (int i = 0; i < 5; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}
Partial initialization fills remaining elements with 0.
1 2 0 0 0
Question 3
Easy
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {5, 10, 15, 20};
    cout << sizeof(arr) << endl;
    cout << sizeof(arr) / sizeof(arr[0]) << endl;
    return 0;
}
4 ints * 4 bytes = 16 bytes. 16 / 4 = 4 elements.
16
4
Question 4
Medium
What is the output?
#include <iostream>
using namespace std;
void func(int arr[]) {
    cout << sizeof(arr) << endl;
}
int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    cout << sizeof(arr) << endl;
    func(arr);
    return 0;
}
In the function, arr decays to a pointer.
20
8
Question 5
Medium
What is the output?
#include <iostream>
using namespace std;
void modify(int arr[]) {
    arr[0] = 99;
}
int main() {
    int arr[] = {1, 2, 3};
    modify(arr);
    cout << arr[0] << endl;
    return 0;
}
Arrays are passed by pointer, so modifications affect the original.
99
Question 6
Medium
What is the output?
#include <iostream>
using namespace std;
int main() {
    int mat[2][3] = {{1, 2, 3}, {4, 5, 6}};
    cout << mat[0][2] << " " << mat[1][0] << endl;
    return 0;
}
mat[row][col]. Row 0 col 2 = 3. Row 1 col 0 = 4.
3 4
Question 7
Medium
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {5, 3, 8, 1, 9, 2};
    int n = 6;
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    cout << maxVal << endl;
    return 0;
}
Track the running maximum through the array.
9
Question 8
Medium
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {4, 2, 7, 1, 5};
    int n = 5;
    // One pass of bubble sort
    for (int j = 0; j < n - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            swap(arr[j], arr[j + 1]);
        }
    }
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}
One pass of bubble sort moves the largest element to the end.
2 4 1 5 7
Question 9
Easy
What is the difference between int arr[5]; declared locally vs globally?
Think about initialization and memory location.
A local (inside main/function) array is stored on the stack and contains garbage values (uninitialized). A global (outside all functions) array is stored in the data segment and is automatically initialized to 0. Global arrays can also be much larger without stack overflow.
Question 10
Medium
Why is binary search O(log n) while linear search is O(n)?
How many elements does each eliminate per step?
Linear search checks elements one by one -- worst case checks all n elements. Binary search halves the search range each step by comparing with the middle element. After k steps, the range is n/2^k. When n/2^k = 1, k = log2(n). So binary search needs at most log2(n) comparisons.
Question 11
Hard
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[3] = {10, 20, 30};
    int* ptr = arr;
    cout << *ptr << " " << *(ptr + 1) << " " << *(ptr + 2) << endl;
    return 0;
}
An array name is a pointer to the first element. Pointer arithmetic accesses subsequent elements.
10 20 30
Question 12
Hard
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;
    int left = 0, right = n - 1;
    while (left < right) {
        swap(arr[left], arr[right]);
        left++;
        right--;
    }
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}
Two-pointer technique for reversing.
5 4 3 2 1
Question 13
Hard
What is the difference between int arr[5] and vector<int> vec(5)?
Think about size flexibility, memory location, and bounds checking.
Array: fixed size (5), stored on stack (local) or data segment (global), no bounds checking, sizeof gives total bytes (20). Vector: dynamic size (can grow/shrink), stored on heap, at() provides bounds checking, sizeof gives struct size (24), provides size(), push_back(), and other member functions.
Question 14
Hard
What is the output?
#include <iostream>
using namespace std;
int main() {
    int a[2][2] = {{1, 2}, {3, 4}};
    cout << sizeof(a) << endl;
    cout << sizeof(a[0]) << endl;
    cout << sizeof(a[0][0]) << endl;
    return 0;
}
a is 2x2 = 4 ints. a[0] is a row of 2 ints. a[0][0] is one int.
16
8
4
Question 15
Easy
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[5] = {};
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}
Empty braces {} zero-initialize the array in C++11.
0 0 0 0 0
Question 16
Easy
Write a function that takes an integer array and its size, and returns the sum of all elements.
Loop through the array and accumulate the sum.
#include <iostream>
using namespace std;
int arraySum(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) sum += arr[i];
    return sum;
}
int main() {
    int arr[] = {3, 7, 2, 8, 5};
    cout << arraySum(arr, 5) << endl;
    return 0;
}
Output: 25
Question 17
Medium
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int low = 0, high = 4, target = 5;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) {
            cout << "Found at " << mid << endl;
            break;
        }
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return 0;
}
Binary search: mid = (0+4)/2 = 2. arr[2] = 5 == target.
Found at 2
Question 18
Medium
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {3, 1, 4, 1, 5};
    int n = 5;
    // Selection sort: find min and place at front
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        swap(arr[i], arr[minIdx]);
    }
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}
Selection sort finds the minimum in the unsorted portion and places it at the beginning.
1 1 3 4 5
Question 19
Easy
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[3];
    arr[0] = 10;
    arr[1] = 20;
    arr[2] = 30;
    cout << arr[0] + arr[1] + arr[2] << endl;
    return 0;
}
Elements are assigned individually, then summed.
60
Question 20
Hard
What is the output?
#include <iostream>
using namespace std;
int arr[5];  // Global
int main() {
    int brr[5];  // Local
    cout << arr[0] << endl;
    // cout << brr[0]; // Garbage!
    return 0;
}
Global arrays are zero-initialized. Local arrays are not.
0
Question 21
Medium
What is the difference between arr[i] and *(arr + i) in C++?
Think about pointer arithmetic and array access.
They are exactly equivalent. arr[i] is syntactic sugar for *(arr + i). The array name arr decays to a pointer to the first element. Adding i advances the pointer by i * sizeof(element) bytes. Dereferencing with * gives the value.
Question 22
Medium
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {10, 20, 30, 40, 50};
    int n = 5;
    int sum = 0;
    for (int i = 0; i < n; i += 2) {
        sum += arr[i];
    }
    cout << sum << endl;
    return 0;
}
The loop increments by 2, so it visits indices 0, 2, 4.
90
Question 23
Hard
What is the output?
#include <iostream>
using namespace std;
int main() {
    int a[2][3] = {{1,2,3},{4,5,6}};
    cout << a[0][2] + a[1][0] << endl;
    cout << sizeof(a) / sizeof(a[0][0]) << endl;
    return 0;
}
a[0][2] is 3, a[1][0] is 4. Total elements = 2*3 = 6.
7
6

Mixed & Application Questions

Question 1
Easy
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[4] = {10, 20, 30, 40};
    arr[1] = 99;
    cout << arr[1] << endl;
    return 0;
}
Array elements can be modified by index.
99
Question 2
Easy
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {5, 10, 15};
    for (int x : arr) {
        cout << x * 2 << " ";
    }
    cout << endl;
    return 0;
}
Range-based for loop iterates over all elements. x is a copy.
10 20 30
Question 3
Medium
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[3][3] = {
        {1, 0, 0},
        {0, 1, 0},
        {0, 0, 1}
    };
    int trace = 0;
    for (int i = 0; i < 3; i++) {
        trace += arr[i][i];
    }
    cout << trace << endl;
    return 0;
}
The trace is the sum of diagonal elements (where row == column).
3
Question 4
Easy
Write a program that reads 5 integers into an array and prints them in reverse order.
Read into arr[0..4], then print from arr[4] down to arr[0].
#include <iostream>
using namespace std;
int main() {
    int arr[5];
    for (int i = 0; i < 5; i++) cin >> arr[i];
    for (int i = 4; i >= 0; i--) cout << arr[i] << " ";
    cout << endl;
    return 0;
}
Input: 1 2 3 4 5 Output: 5 4 3 2 1
Question 5
Medium
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = 5;
    // Prefix sum
    for (int i = 1; i < n; i++) {
        arr[i] += arr[i - 1];
    }
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}
Each element becomes the sum of all elements up to and including itself.
2 6 12 20 30
Question 6
Hard
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = 5;
    // Insertion sort
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}
Insertion sort inserts each element into its correct position in the sorted portion.
1 2 5 8 9
Question 7
Medium
Write a function that takes a 2D array (3x3) and prints the transpose (rows become columns).
Transpose: transposed[j][i] = original[i][j].
#include <iostream>
using namespace std;
int main() {
    int mat[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    int trans[3][3];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            trans[j][i] = mat[i][j];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++)
            cout << trans[i][j] << " ";
        cout << endl;
    }
    return 0;
}
Output: 1 4 7 2 5 8 3 6 9
Question 8
Hard
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};
    int n = 6, target = 7;
    int low = 0, high = n - 1, steps = 0;
    while (low <= high) {
        steps++;
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            cout << "Found at " << mid << " in " << steps << " steps" << endl;
            break;
        }
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return 0;
}
Trace binary search: mid = 2, arr[2]=5 < 7, mid = 4, arr[4]=9 > 7, mid = 3, arr[3]=7 found.
Found at 3 in 3 steps
Question 9
Hard
Write a program that reads n integers and finds the second largest element without sorting.
Track both the largest and second largest in one pass.
#include <iostream>
#include <climits>
using namespace std;
int main() {
    int n;
    cin >> n;
    int arr[100];
    for (int i = 0; i < n; i++) cin >> arr[i];
    int first = INT_MIN, second = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (arr[i] > first) {
            second = first;
            first = arr[i];
        } else if (arr[i] > second && arr[i] != first) {
            second = arr[i];
        }
    }
    cout << "Second largest: " << second << endl;
    return 0;
}
Input: 5 12 35 1 10 34 Output: Second largest: 34
Question 10
Medium
Why should you use mid = low + (high - low) / 2 instead of mid = (low + high) / 2 in binary search?
Think about what happens when low and high are both large.
(low + high) can overflow if both are close to INT_MAX. For example, if low = 2 billion and high = 2 billion, their sum exceeds INT_MAX and overflows. low + (high - low) / 2 computes the difference first (which fits in int) and avoids overflow.
Question 11
Easy
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[5] = {0};
    arr[2] = 42;
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}
{0} initializes all elements to 0. Then one element is changed.
0 0 42 0 0
Question 12
Hard
What is the output?
#include <iostream>
using namespace std;
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;
    // Left rotate by 2
    int temp1 = arr[0], temp2 = arr[1];
    for (int i = 0; i < n - 2; i++) {
        arr[i] = arr[i + 2];
    }
    arr[n - 2] = temp1;
    arr[n - 1] = temp2;
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}
Left rotation by 2 moves first 2 elements to the end.
3 4 5 1 2

Multiple Choice Questions

MCQ 1
What is the index of the last element in int arr[10]?
  • A. 10
  • B. 9
  • C. 11
  • D. 0
Answer: B
B is correct. Arrays are 0-indexed. An array of size 10 has indices 0 through 9. Accessing arr[10] is out of bounds.
MCQ 2
What does int arr[5] = {1, 2}; initialize the remaining elements to?
  • A. Garbage values
  • B. 1
  • C. 0
  • D. -1
Answer: C
C is correct. Partial initialization fills remaining elements with 0. So arr = {1, 2, 0, 0, 0}.
MCQ 3
What is the time complexity of accessing arr[i]?
  • A. O(n)
  • B. O(log n)
  • C. O(1)
  • D. O(n^2)
Answer: C
C is correct. Array access is O(1) because the address is calculated directly: base_address + i * sizeof(element). No iteration is needed.
MCQ 4
What happens when an array is passed to a function in C++?
  • A. A copy of the array is created
  • B. It decays to a pointer to the first element
  • C. The function receives a reference
  • D. Compilation error
Answer: B
B is correct. Arrays decay to pointers when passed to functions. The function receives a pointer to arr[0], not a copy. Changes made inside the function affect the original array.
MCQ 5
What is the time complexity of binary search?
  • A. O(n)
  • B. O(n^2)
  • C. O(log n)
  • D. O(n log n)
Answer: C
C is correct. Binary search halves the search range each step, giving O(log n) time complexity. It requires the array to be sorted.
MCQ 6
What is the time complexity of bubble sort in the worst case?
  • A. O(n)
  • B. O(n log n)
  • C. O(n^2)
  • D. O(log n)
Answer: C
C is correct. Bubble sort has two nested loops, each up to n iterations. Worst case (reverse sorted array) requires O(n^2) comparisons and swaps.
MCQ 7
How are elements of a 2D array int a[3][4] stored in memory?
  • A. Column-major order
  • B. Row-major order
  • C. Random order
  • D. Depends on the compiler
Answer: B
B is correct. C++ stores 2D arrays in row-major order: all elements of row 0 first, then row 1, then row 2. This affects cache performance when iterating.
MCQ 8
What is sizeof(arr) inside a function where arr is passed as int arr[] on a 64-bit system?
  • A. Size of the entire array
  • B. 4
  • C. 8
  • D. 0
Answer: C
C is correct. Inside the function, arr is a pointer (not an array). On a 64-bit system, sizeof(pointer) = 8 bytes, regardless of the original array size.
MCQ 9
Which sorting algorithm has the best performance on a nearly sorted array?
  • A. Bubble sort
  • B. Selection sort
  • C. Insertion sort
  • D. All are equal
Answer: C
C is correct. Insertion sort has O(n) best-case performance on a nearly sorted array because the inner while loop rarely executes. Bubble sort (with optimization) is also O(n) best case, but insertion sort is generally faster in practice.
MCQ 10
Why should large arrays in competitive programming be declared globally?
  • A. Global arrays are faster to access
  • B. Global arrays are auto-initialized to 0 and avoid stack overflow
  • C. Global arrays support dynamic sizing
  • D. Global arrays have bounds checking
Answer: B
B is correct. Local arrays go on the stack (limited to ~1-8 MB). Global arrays go in the data segment (much larger). Global arrays are also automatically zero-initialized, avoiding garbage values.
MCQ 11
What is the correct way to get the number of elements in an array int arr[10]?
  • A. arr.length()
  • B. arr.size()
  • C. sizeof(arr) / sizeof(arr[0])
  • D. len(arr)
Answer: C
C is correct. C++ arrays do not have member functions like length() or size(). sizeof(arr) gives total bytes, divided by sizeof(one element) gives the count.
MCQ 12
When passing a 2D array to a function, which dimension can be omitted?
  • A. Both dimensions
  • B. The row dimension (first)
  • C. The column dimension (second)
  • D. Neither
Answer: B
B is correct. The column dimension must be specified for the compiler to calculate memory offsets. void f(int arr[][4], int rows) is valid. void f(int arr[][], int rows, int cols) is NOT valid.
MCQ 13
What does int arr[5] = {}; do in C++11?
  • A. Creates an empty array
  • B. Zero-initializes all 5 elements
  • C. Compilation error
  • D. Leaves elements uninitialized
Answer: B
B is correct. In C++11, empty brace initialization = {} zero-initializes all elements. The array has 5 elements, all set to 0.
MCQ 14
What is the best-case time complexity of insertion sort?
  • A. O(n^2)
  • B. O(n log n)
  • C. O(n)
  • D. O(1)
Answer: C
C is correct. When the array is already sorted, insertion sort's inner while loop never executes. Each element is compared once with its predecessor and stays in place. Total: O(n) comparisons.
MCQ 15
What is the maximum size of a local array (on the stack) in most systems?
  • A. ~100 elements
  • B. ~10,000 elements
  • C. ~250,000 elements (about 1 MB for int)
  • D. Unlimited
Answer: C
C is correct. The default stack size is typically 1-8 MB. For int arrays (4 bytes each), ~250,000 elements fit in 1 MB. For larger arrays, use global declaration or dynamic allocation.
MCQ 16
In binary search, what does low + (high - low) / 2 avoid compared to (low + high) / 2?
  • A. Division by zero
  • B. Integer overflow
  • C. Negative indices
  • D. Off-by-one errors
Answer: B
B is correct. If low and high are both close to INT_MAX, low + high overflows. low + (high - low) / 2 computes the difference first, which is always non-negative and fits in an int.
MCQ 17
What is the time complexity of linear search?
  • A. O(1)
  • B. O(log n)
  • C. O(n)
  • D. O(n^2)
Answer: C
C is correct. Linear search checks each element one by one. In the worst case, it checks all n elements before finding the target (or confirming absence).
MCQ 18
Which sorting algorithm is stable (preserves relative order of equal elements)?
  • A. Selection sort
  • B. Insertion sort
  • C. Neither
  • D. Both
Answer: B
B is correct. Insertion sort is stable because it only moves elements past those that are strictly greater. Selection sort is NOT stable because the swap operation can change the relative order of equal elements.

Coding Challenges

Challenge 1: Array Rotation

Easy
Write a program that left rotates an array by k positions. Read n (array size), k (rotation count), and n integers. Print the rotated array.
Sample Input
5 2 1 2 3 4 5
Sample Output
3 4 5 1 2
1 <= n <= 1000, 0 <= k <= n. Use O(n) extra space.
#include <iostream>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    int arr[1000], temp[1000];
    for (int i = 0; i < n; i++) cin >> arr[i];
    for (int i = 0; i < n; i++) temp[i] = arr[(i + k) % n];
    for (int i = 0; i < n; i++) cout << temp[i] << " ";
    cout << endl;
    return 0;
}

Challenge 2: Merge Two Sorted Arrays

Medium
Given two sorted arrays of sizes n and m, merge them into a single sorted array without using any sorting function. Print the merged array.
Sample Input
3 4 1 3 5 2 4 6 8
Sample Output
1 2 3 4 5 6 8
Use the two-pointer merge technique. O(n+m) time.
#include <iostream>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    int a[1000], b[1000], c[2000];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) c[k++] = a[i++];
        else c[k++] = b[j++];
    }
    while (i < n) c[k++] = a[i++];
    while (j < m) c[k++] = b[j++];
    for (int i = 0; i < k; i++) cout << c[i] << " ";
    cout << endl;
    return 0;
}

Challenge 3: Matrix Diagonal Sum

Medium
Read a square matrix of size n x n. Print the sum of the primary diagonal (top-left to bottom-right) and the secondary diagonal (top-right to bottom-left). If n is odd, subtract the center element once (it is counted in both diagonals).
Sample Input
3 1 2 3 4 5 6 7 8 9
Sample Output
Primary diagonal sum: 15 Secondary diagonal sum: 15 Total (without double-counting center): 25
1 <= n <= 100. Handle odd n to avoid double-counting the center element.
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int mat[100][100];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> mat[i][j];
    int primary = 0, secondary = 0;
    for (int i = 0; i < n; i++) {
        primary += mat[i][i];
        secondary += mat[i][n - 1 - i];
    }
    int total = primary + secondary;
    if (n % 2 == 1) total -= mat[n/2][n/2];
    cout << "Primary diagonal sum: " << primary << endl;
    cout << "Secondary diagonal sum: " << secondary << endl;
    cout << "Total (without double-counting center): " << total << endl;
    return 0;
}

Challenge 4: Find Duplicate in Array

Medium
Given an array of n integers where each element is between 1 and n-1, find the duplicate element. There is exactly one duplicate. Do NOT use extra space (no hash map or extra array).
Sample Input
5 1 3 4 2 2
Sample Output
Duplicate: 2
O(n) time, O(1) space. Use the tortoise and hare (Floyd's cycle detection) approach.
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int arr[100001];
    for (int i = 0; i < n; i++) cin >> arr[i];
    // Floyd's cycle detection
    int slow = arr[0], fast = arr[0];
    do {
        slow = arr[slow];
        fast = arr[arr[fast]];
    } while (slow != fast);
    slow = arr[0];
    while (slow != fast) {
        slow = arr[slow];
        fast = arr[fast];
    }
    cout << "Duplicate: " << slow << endl;
    return 0;
}

Challenge 5: Spiral Matrix Print

Hard
Read a matrix of size m x n and print its elements in spiral order (clockwise: right, down, left, up, repeat).
Sample Input
3 4 1 2 3 4 5 6 7 8 9 10 11 12
Sample Output
1 2 3 4 8 12 11 10 9 5 6 7
Handle rectangular matrices (not necessarily square). Use four boundary variables.
#include <iostream>
using namespace std;
int main() {
    int m, n;
    cin >> m >> n;
    int mat[100][100];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> mat[i][j];
    int top = 0, bottom = m - 1, left = 0, right = n - 1;
    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; j++) cout << mat[top][j] << " ";
        top++;
        for (int i = top; i <= bottom; i++) cout << mat[i][right] << " ";
        right--;
        if (top <= bottom) {
            for (int j = right; j >= left; j--) cout << mat[bottom][j] << " ";
            bottom--;
        }
        if (left <= right) {
            for (int i = bottom; i >= top; i--) cout << mat[i][left] << " ";
            left++;
        }
    }
    cout << endl;
    return 0;
}

Challenge 6: Kadane's Algorithm - Maximum Subarray Sum

Hard
Given an array of n integers (may include negatives), find the contiguous subarray with the maximum sum. Print the maximum sum and the subarray boundaries.
Sample Input
8 -2 1 -3 4 -1 2 1 -5
Sample Output
Maximum subarray sum: 6 Subarray: index 3 to 6
Use Kadane's algorithm. O(n) time, O(1) space.
#include <iostream>
#include <climits>
using namespace std;
int main() {
    int n;
    cin >> n;
    int arr[100000];
    for (int i = 0; i < n; i++) cin >> arr[i];
    int maxSum = INT_MIN, currentSum = 0;
    int start = 0, end = 0, tempStart = 0;
    for (int i = 0; i < n; i++) {
        currentSum += arr[i];
        if (currentSum > maxSum) {
            maxSum = currentSum;
            start = tempStart;
            end = i;
        }
        if (currentSum < 0) {
            currentSum = 0;
            tempStart = i + 1;
        }
    }
    cout << "Maximum subarray sum: " << maxSum << endl;
    cout << "Subarray: index " << start << " to " << end << endl;
    return 0;
}

Need to Review the Concepts?

Go back to the detailed notes for this chapter.

Read Chapter Notes

Want to learn C++ with a live mentor?

Explore our C++ Masterclass