Mini-project Part 2: Flowcharting an OSN Problem

This project uses all of Part 2: abstraction, flowcharts, pseudocode, tracing, and counting the number of steps. The code is short — what is judged is the plan made before the code is written.

The problem

Buildings and the sunrise. Along a street stand n buildings in a row from west to east. Building i has height t[i]. The sun rises in the east. A building can see the sunrise if there is no building to its east whose height is greater than or equal to its own height.

Input. The first line contains n. The second line contains n integers t[1..n], from the westernmost building to the easternmost.

Output. One line containing the number of buildings that can see the sunrise.

Constraints. 1 ≤ n ≤ 1,000,000, and 1 ≤ t[i] ≤ 10⁹.

Sample input:

6
3 7 8 3 6 1

Sample output:

3

The ones that can see: building 3 (height 8), building 5 (height 6), and building 6 (height 1). Buildings 1 and 2 are blocked by the building of height 8; building 4 is blocked by the building of height 6.

What to do

Four things, in order. Do not jump to number 4.

  1. Abstraction. Rewrite the problem as one sentence "given ... print ...", without buildings and without the sun.
  2. Flowchart. Draw your algorithm on paper. It must have one start oval, one end oval, at least one diamond, and one back arrow.
  3. Pseudocode. Write the same algorithm in written form, using the keywords from Chapter 09. Then trace it by hand using the sample above and build its tracing table.
  4. Code. Only after that, write the program in starter.cpp.

Before writing code, first answer these in a comment at the top of the file:

  • What is the number of steps of your algorithm in O notation?
  • For n = 1,000,000, does that fit within one second?

Hints

  • Think from the east side. The easternmost building can always see.
  • Traverse from the back while keeping just one value: the greatest height seen so far.
  • A solution that checks, for each building, all buildings to its east is O(n²) — 10¹² steps for this problem's constraints. The table in Chapter 10 says that will not finish.
  • n can be up to one million: use a global array, and "\n" not endl.

Edge cases you must test

Input Correct answer
1 / 5 1
4 / 5 5 5 5 1
4 / 1 2 3 4 1
4 / 4 3 2 1 4

The last row explains why the problem uses the words "greater than or equal to": a building of the same height still blocks.

Files

Compile and run:

g++ -std=c++17 -O2 -o gedung projects/02-flowchart/starter.cpp
./gedung < projects/02-flowchart/contoh-masukan.txt

Done?

If all four edge cases in the table are correct, your flowchart and pseudocode have been drawn, and you can explain why your algorithm is O(n) — this project is finished.

Continue to Chapter 11 — Brute force, where plans start turning into solution strategies that have names.