Start learning free

LESSON 250 OF 667 · NESTED LOOPS

Top K Brands V4 in C++: Repeating the Search to Rank k Brands

Practice Read the full explanation

Show the top k brands by rating. This is v3's search, repeated k times: find the best brand, mark it as taken, then search again among the brands that are not taken yet, until you have k brands in rank order.

You start with:

vector<string> brands = {"TechPro", "MegaCorp", "Quantum", "NeoByte", "Zenith"};
vector<int> ratings = {4, 5, 3, 5, 4};
int k = 3;

Build:

1. MegaCorp (5)
2. NeoByte (5)
3. TechPro (4)

Rules:

  • Repeat v3's search k times. Each round looks only at brands that are not taken yet and picks the one with the highest rating, then marks it as taken (one true/false flag per brand).
  • Ties go to the brand listed first: keep the first brand you find and replace it only on a strictly higher rating.
  • k is never larger than the number of brands.
  • Each line is "rank. Brand (rating)", starting at rank 1.
  • Print the lines, one per line, with cout << ... << endl.

Start with the two declarations vector<bool> used(ratings.size(), false); and vector<string> lines;. A flag tells whether that position is already taken.

Each round is v3's search: nothing found yet, scan every position, skip taken ones, keep the first candidate and replace it only on a strictly higher rating. Then mark the winner as taken and add its line.

vector<string> brands = {"TechPro", "MegaCorp", "Quantum", "NeoByte", "Zenith"};
vector<int> ratings = {4, 5, 3, 5, 4};
int k = 3;

vector<bool> used(ratings.size(), false);
vector<string> lines;
for (int rank = 1; rank <= k; rank++) {
    int bestIndex = -1;
    for (int i = 0; i < (int)ratings.size(); i++) {
        if (!used[i]) {
            if (bestIndex == -1 || ratings[i] > ratings[bestIndex]) {
                bestIndex = i;
            }
        }
    }
    used[bestIndex] = true;
    lines.push_back(to_string(rank) + ". " + brands[bestIndex] + " (" + to_string(ratings[bestIndex]) + ")");
}
for (int i = 0; i < (int)lines.size(); i++) cout << lines[i] << endl;

STEP 1 OF 11
    Ctrl + Enter to check

    C++ · NESTED LOOPS

    Top K Brands V4 in C++, explained

    Problem overview

    Version 4 prints the top k brands by rating. The starter data has two parallel vectors, brands and ratings, where ratings[i] belongs to brands[i], and int k = 3;. Each output line has the form rank. Brand (rating), starting at rank 1. When two brands have the same rating, the one listed first ranks higher. The statement promises that k is never larger than the number of brands.

    With ratings 4, 5, 3, 5 and 4, the program prints:

    1. MegaCorp (5)
    2. NeoByte (5)
    3. TechPro (4)
    

    The previous version found the single best brand with a loop. This version finds it k times.

    Approach: search, mark, search again

    You don't need to sort. Find the best brand, mark it as taken, then search again among the brands that aren't taken. The second search finds the second best, the third search the third best, and so on until k brands have been chosen.

    The marks live in a vector<bool> named used, with one flag per brand. The program doesn't print inside the search. It builds each finished line as a string and stores it in a vector<string> called lines, and prints them all at the end.

    The search uses a strict comparison. A brand replaces the current best only when its rating is strictly higher. That means that when ratings tie, the brand found first, the one listed earlier, stays on top, which is the rule from the statement.

    Why not sort?

    Sorting ratings would reorder the numbers but leave brands where it is, so every rating would end up next to the wrong name. A correct sort would have to move both vectors together, and it would also need a way to keep equal ratings in their listed order. The repeated search avoids both problems: the data never moves, and the strict comparison settles ties by itself. The cost is speed, which matters little for five brands.

    Step by step

    1. Create used as vector<bool> used(ratings.size(), false): one false per rating, meaning that nothing is taken yet.
    2. Create an empty vector<string> lines. Lines arrive one per round, so it starts empty.
    3. Write the outer loop with rank from 1 up to and including k. The counter does two jobs: it counts the rounds, and it is the number printed in front of the brand.
    4. Start each round with int bestIndex = -1;, which means no brand is found yet. Every round restarts the search.
    5. Write the inner loop over every position of ratings.
    6. Skip taken brands: an if (!used[i]) lets only the brands that haven't won yet be candidates.
    7. Compare: a second if is true when bestIndex == -1 or when ratings[i] is strictly higher than ratings[bestIndex].
    8. Remember the brand: set bestIndex = i.
    9. Mark the winner after the inner loop: used[bestIndex] = true, so the next round skips it.
    10. Build the line and add it with push_back: the rank, ". ", the brand's name, " (", the rating and ")".
    11. Print every line with a final loop over lines.

    The solution in C++

    vector<string> brands = {"TechPro", "MegaCorp", "Quantum", "NeoByte", "Zenith"};
    vector<int> ratings = {4, 5, 3, 5, 4};
    int k = 3;
    
    vector<bool> used(ratings.size(), false);
    vector<string> lines;
    for (int rank = 1; rank <= k; rank++) {
        int bestIndex = -1;
        for (int i = 0; i < (int)ratings.size(); i++) {
            if (!used[i]) {
                if (bestIndex == -1 || ratings[i] > ratings[bestIndex]) {
                    bestIndex = i;
                }
            }
        }
        used[bestIndex] = true;
        lines.push_back(to_string(rank) + ". " + brands[bestIndex] + " (" + to_string(ratings[bestIndex]) + ")");
    }
    for (int i = 0; i < (int)lines.size(); i++) cout << lines[i] << endl;
    

    Building the text

    C++ can't join a number to text with +: 1 + ". " doesn't produce the text 1. . Each number goes through to_string first. After that, to_string(rank) + ". " + brands[bestIndex] is a string added to a string literal, and the rest of the line follows the same pattern. Because the first operand is already a string, every + after it works.

    Here is how the rounds go on the starter data:

    rankcandidateswinnerwhy
    1all fiveMegaCorp (5)NeoByte also has 5 but comes later
    2all but MegaCorpNeoByte (5)the only 5 left
    3TechPro (4), Quantum (3), Zenith (4)TechPro (4)ties with Zenith, listed first

    The program stores bestIndex, a position, instead of the best rating. A position leads to both the name and the rating, because the two vectors share their indexes, and it is also what used needs to mark the brand as taken.

    Complexity

    Each of the k rounds scans all n brands, so the time is O(k × n). With k close to n, that is about n squared. The extra space is O(n) for used, plus O(k) for lines.

    Edge cases and common mistakes

    • Ties. Using >= instead of > would let the later brand win every tie, and the output would start with NeoByte.
    • Forgetting used[bestIndex] = true. Every round would then return MegaCorp.
    • k equal to the number of brands. With k = 5 the output has five lines: MegaCorp, NeoByte, TechPro, Zenith (4) and Quantum (3). Everybody ranks once.
    • k = 1. The output is the first line only: 1. MegaCorp (5).
    • A k larger than the number of brands. The statement rules this out. This version has no safeguard: a round with nobody left would leave bestIndex at -1 and the program would use used[-1], which is undefined behaviour.
    • Starting rank at 0. The lines would be numbered 0, 1, 2.

    Testing

    Run the starter data for the three lines above. Try k = 1 for one line and k = 5 for all five brands in rank order.

    Keep going with C++650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free