Skip to content
Tutorials Center
My learning

Topics

Lesson 166 of 171 ยท Practice and Review

C++ Programs: Array and Searching Puzzles

C++ array puzzles with output: common elements, prefix sums, Dutch flag sort, wave sort, rotated array search, sorting 2D rows and next greater element.

Array puzzles are small problems with one clever idea each. Often the first solution that comes to mind uses two nested loops; the interesting part is spotting how a set, a running total, two pointers or a binary search replaces the inner loop. This page walks through seven such puzzles with complete, runnable programs, and after each one says what it costs.

All programs use std::vector and the standard algorithms. If you need a refresher, see vectors, searching and sorting and the algorithm catalogue. For the first forty classics, see C++ programs.

When a problem says "sorted" or "contiguous", think of binary search or two pointers. When it says "find a pair" or "have I seen this before", think of a hash set or a hash map. Those two thoughts solve most array interview questions.

1. Common elements of two arrays

Put one array in a std::unordered_set, then walk the other and keep the values that are in the set. Erasing a value after it is reported prevents duplicates in the result. Cost: O(n + m) on average, instead of O(n * m) for two loops.

C++ 1. Common elements

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

2. Prefix sums for range queries

A prefix array stores pre[i] = a[0] + ... + a[i - 1]. The sum of a[l..r] is then pre[r + 1] - pre[l]: one subtraction per query after a single pass. std::partial_sum builds the array for you.

C++ 2. Range sums with prefix sums

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

3. Sort an array of 0s, 1s and 2s (Dutch national flag)

Sorting three distinct values does not need std::sort. Keep three regions with three indexes: everything before low is 0, everything after high is 2, and mid scans the unknown middle. A 0 is swapped to the front, a 2 to the back, a 1 is left in place. One pass, O(n) time, O(1) memory.

C++ 3. Dutch national flag

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Notice the asymmetry: after swapping a 2 to the back, mid stays where it is, because the value that arrived from the back has not been inspected yet. After swapping a 0 forward, mid can advance, because the value that arrived from low is always a 1 that was already examined.

4. Wave sort

Rearrange the array so that a[0] >= a[1] <= a[2] >= a[3] .... You do not need a full sort: visit every even position and make sure it is at least as large as both neighbours, swapping with any neighbour that is larger. One pass, O(n).

C++ 4. Wave sort

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

5. Search in a rotated sorted array

A sorted array such as 1 2 3 4 5 6 7 rotated to 5 6 7 1 2 3 4 is no longer fully sorted, but at every step of a binary search at least one half is still sorted. Check which half is sorted, decide whether the target lies inside it, and discard the other half. Cost: O(log n). This version assumes distinct values.

C++ 5. Rotated array search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

6. Sort every row of a 2D array

A vector<vector<int>> is a vector of rows, so each row is an ordinary vector that you can pass to std::ranges::sort. To sort the whole matrix as one list, flatten it, sort once and copy back; to sort only the rows, loop over them.

C++ 6. Sort rows of a matrix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

The second sort uses a projection: the lambda extracts the key (the row's last element) and std::ranges::greater{} compares those keys. No custom comparator with two parameters is needed.

7. Next greater element with a stack

For each element, find the first larger value to its right, or -1 if none exists. Scanning right to left with a stack of candidates gives O(n): pop everything not larger than the current value, then the stack top (if any) is the answer; push the current value so later elements can use it. Every element is pushed and popped at most once.

C++ 7. Next greater element

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

See stack, queue and priority queue for the container used here.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the Dutch national flag loop, why does mid stay in place after swapping a 2 with a[high]?

    a[high] was never inspected, so after the swap a[mid] holds an unknown value that must be checked on the next iteration.
  2. 2. What is the time complexity of searching a rotated sorted array (distinct values) with the method shown?

    Each step discards half of the range because one half is always sorted, exactly like an ordinary binary search.
  3. 3. With pre built from std::partial_sum into pre.begin() + 1, which expression gives the sum of a[l..r]?

    pre[i] is the sum of the first i elements, so the sum of a[l..r] is pre[r + 1] minus pre[l].
  4. 4. Why is next-greater-element O(n) even though it contains a while loop inside a for loop?

    The total number of pops cannot exceed the total number of pushes, which is n.

Summary

  • A hash set turns an O(n * m) "is it in the other array" loop into O(n + m).
  • Prefix sums answer any range-sum query with one subtraction; std::partial_sum builds them.
  • The Dutch national flag sort partitions 0, 1 and 2 in one pass with three indexes.
  • Wave sort only needs local swaps at every second position.
  • In a rotated sorted array, one half is always sorted, so binary search still works in O(log n).
  • Ranges projections let you sort rows by any key; a monotonic stack finds next-greater values in O(n).

Next: C++ Programs: String Tasks.