Master Hash Maps: C++ vs Python

Solve LeetCode 560 in C++ and Python using prefix sum and hash maps.

Introduction

30 Second Summary

When you're solving coding challenges under time pressure, the difference between a solution that passes and one that times out often comes down to picking the right data structure. Hash maps are behind most of the fastest patterns in competitive programming.

In this project, you will solve a classic interview problem (Subarray Sum Equals K) in both C++ and Python, measure their performance side by side, and discover when the "fastest" hash map can actually become the slowest.

What You'll Build

You will have a dual-language competitive programming workspace where you run a single command and see both your C++ and Python solutions execute with their runtimes printed side by side, proving which language and which container wins on each problem.

By the end of this project, you'll have:

  • A competitive programming workspace with built-in millisecond timing that lets you write, compile, and benchmark solutions in both C++ and Python from a single folder.
  • A solved LeetCode 560 (Subarray Sum Equals K) using the prefix sum + hash map technique, with measurable proof that it crushes the brute-force approach on large inputs.
  • A tested understanding of when unordered_map can be slower than map in contests, and how a custom hash function fixes it.
  • Secret Mission: Solve LeetCode 974 (Subarray Sums Divisible by K) using a modulo variation of the prefix sum technique.

Are there any prerequisites?

You should be comfortable with basic C++ and Python syntax (variables, loops, arrays, functions). You should also know how to compile and run code from the terminal.

No competitive programming experience is required. This project teaches you the patterns from scratch.

Before We Start

Before We Start...

Before we dive in, let's lock in what you're about to build and why it matters.

Solving competitive programming problems in two languages at once forces you to see past syntax and into the underlying algorithm. Take a moment to commit to what you're building here.

Set Up Your Dual-Language CP Workspace

Competitive programming is a race against two clocks: the time limit your code must beat, and the minutes you spend fumbling with tools instead of thinking about algorithms.

In this step, you will build a dual-language workspace with built-in timing so you can write, compile, and compare C++ and Python solutions without friction.

In this step, get ready to:
  • Create a project folder with separate directories for C++ and Python solutions.
  • Write a C++ template with fast I/O and millisecond-precision timing.
  • Write a Python template with equivalent timing and verify both work.
Create the project folder structure

Every contest problem gets its own solution file, so you need a clean folder structure that separates your C++ and Python code from the start.

  • Move to your Desktop by running this command:
cd ~/Desktop
  • Create your project folder and move into it by running these commands:
mkdir cp-hashmaps
cd cp-hashmaps
  • Create the C++ and Python subdirectories by running:
mkdir cpp python
  • Confirm the folders exist by running:
ls

You should see cpp and python listed in the output.

  • Open this folder in VS Code by running:
code .

Don't see both folders?

Make sure you ran mkdir cpp python from inside the cp-hashmaps folder, not from your Desktop. Run pwd to check your current location.

Help me figure out where my folders were created

Write and compile the C++ template

Your C++ template needs two things: fast I/O to avoid time-limit penalties on large inputs, and precise timing so you can measure how long your solution takes.

  • In VS Code, create a new file called template.cpp inside the cpp folder.
  • Paste the following code into cpp/template.cpp:
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto start = chrono::steady_clock::now();

    cout << "Setup OK" << endl;

    auto end = chrono::steady_clock::now();
    chrono::duration<double, milli> elapsed = end - start;
    cerr << "Time: " << fixed << setprecision(3) << elapsed.count() << " ms" << endl;
    return 0;
}

What does this code do?

  • ios_base::sync_with_stdio(false) and cin.tie(nullptr) disable the sync between C and C++ I/O streams. This makes reading input significantly faster in contests.
  • chrono::steady_clock::now() captures timestamps before and after your solution logic. The difference gives you millisecond-precision elapsed time.
  • The timing output goes to cerr (standard error) so it stays separate from your actual solution output on cout. Online judges read your answer without seeing timing noise.
  • Save cpp/template.cpp.
  • Compile the template by running this command in your terminal:
g++ -std=c++17 -O2 cpp/template.cpp -o cpp/template

What do these flags do?

  • -std=c++17 enables the C++17 standard, which matches most online judge settings.
  • -O2 enables optimization level 2. This is what competitive programming judges typically compile with.
  • -o cpp/template names the output executable so it lives alongside the source file.
  • Run your compiled template:
./cpp/template

You should see Setup OK printed to your terminal, followed by a timing line on stderr showing something like Time: 0.004 ms.

Seeing a compilation error?

Check that you included #include <bits/stdc++.h> at the top. This header pulls in all standard library headers and is standard practice in competitive programming with g++.

If you see a "file not found" error for the source file, make sure your terminal is in the cp-hashmaps folder (run pwd to check).

Help me debug my C++ compilation error

✔️ Awesome, I've got everything!

Great. Double check you have saved cpp/template.cpp and that your compiled executable runs without errors.

ⓧ I'd like to double check the full code

Here is the complete cpp/template.cpp file:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto start = chrono::steady_clock::now();

    cout << "Setup OK" << endl;

    auto end = chrono::steady_clock::now();
    chrono::duration<double, milli> elapsed = end - start;
    cerr << "Time: " << fixed << setprecision(3) << elapsed.count() << " ms" << endl;
    return 0;
}
Write and run the Python template

Your Python template mirrors the C++ one: fast input reading via sys.stdin and precise timing via time.perf_counter(). This gives you a fair comparison between the two languages.

  • In VS Code, create a new file called template.py inside the python folder.
  • Paste the following code into python/template.py:
import sys
import time

def main():
    input = sys.stdin.readline
    start = time.perf_counter()

    print("Setup OK")

    end = time.perf_counter()
    print(f"Time: {(end - start) * 1000:.3f} ms", file=sys.stderr)

if __name__ == "__main__":
    main()

What does this code do?

  • input = sys.stdin.readline rebinds input to a faster reader. The built-in input() function has extra overhead that adds up on large inputs.
  • time.perf_counter() provides the highest-resolution timer available on your system. It is the Python equivalent of chrono::steady_clock in C++.
  • Timing goes to sys.stderr via file=sys.stderr for the same reason as the C++ version: it keeps timing separate from solution output.
  • Save python/template.py.

Before you run this, what do you expect to see in the terminal? Think about what both the stdout and stderr outputs should look like.

  • Run your Python template:
python3 python/template.py

You should see Setup OK followed by a timing line like Time: 0.015 ms. Both languages now report their execution time in the same format.

Seeing a syntax error or file not found?

Make sure you are running with python3 (not python). The f-string syntax requires Python 3.6 or later.

If you see "No such file or directory", confirm your terminal is still in the cp-hashmaps folder by running pwd.

Help me fix my Python template error

✔️ Awesome, I've got everything!

Great. Double check you have saved python/template.py and that running it prints Setup OK with a timing line.

ⓧ I'd like to double check the full code

Here is the complete python/template.py file:

import sys
import time

def main():
    input = sys.stdin.readline
    start = time.perf_counter()

    print("Setup OK")

    end = time.perf_counter()
    print(f"Time: {(end - start) * 1000:.3f} ms", file=sys.stderr)

if __name__ == "__main__":
    main()

Your dual-language workspace is ready. You have C++ and Python templates that both report their execution time in the same format. Next up, you will use these templates to solve a frequency-counting problem and see your first real timing difference between the two languages.

Solve a Frequency Count Problem in Both Languages

Your dual-language workspace is set up and timing is verified. Now it is time to solve your first real problem with it.

Frequency counting is the simplest hash map pattern and the foundation for every harder problem you will tackle later. By solving it in both C++ and Python, you will compare the idiomatic containers (unordered_map vs Counter) and see your first measurable timing difference between the two languages.

In this step, get ready to:
  • Write a frequency counter in C++ and Python and verify both produce correct output.
  • Generate a large test input and compare execution times between both languages.
  • Observe and record the performance gap between compiled C++ and interpreted Python.
Write the C++ frequency counter

The problem is straightforward: read an array of integers, count how many times each number appears, and print the results. In C++, the idiomatic container for this is unordered_map, which gives average O(1) lookup and insertion.

  • Create a new file called frequency.cpp inside your cpp/ folder.
  • Paste the following code into it:
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto start = chrono::steady_clock::now();

    // Read the count of numbers
    int n;
    cin >> n;
    // Store frequency of each number in a hash map
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        freq[x]++;
    }

    // Print each value and its count
    for (auto& [val, cnt] : freq) {
        cout << val << ": " << cnt << "\n";
    }

    auto end = chrono::steady_clock::now();
    chrono::duration<double, milli> elapsed = end - start;
    cerr << "Time: " << fixed << setprecision(3) << elapsed.count() << " ms" << endl;
    return 0;
}

What does this code do?

This solution follows the same timing template you built in Step 1, with the core logic sandwiched between the clock calls.

  • unordered_map<int, int> freq creates a hash map where keys are the numbers and values are their counts.
  • freq[x]++ increments the count for number x. If the key does not exist yet, it gets initialized to 0 first.
  • auto& [val, cnt] uses C++17 structured bindings to iterate over each key-value pair.

Before you can run it, you need a small test input file to verify correctness.

  • Create a file called test_freq.txt in your project root by running:
echo "8
1 2 3 2 1 3 3 4" > test_freq.txt
  • Compile and run your C++ solution against the test input:
g++ -std=c++17 -O2 -o cpp/frequency cpp/frequency.cpp
./cpp/frequency < test_freq.txt

You should see each number and its frequency printed. The numbers 1, 2, and 3 each appear 2, 2, and 3 times respectively, and 4 appears once. The exact ordering may vary since unordered_map does not guarantee order.

Seeing a compilation error?

  • If you see an error about structured bindings, make sure you used the -std=c++17 flag. Structured bindings require C++17.
  • Check that you typed auto& [val, cnt] with square brackets, not parentheses.

Why won't my frequency.cpp compile?

Write the Python frequency counter

Python's idiomatic approach to frequency counting is collections.Counter. It is a dict subclass that counts hashable objects in a single call.

  • Create a new file called frequency.py inside your python/ folder.
  • Paste the following code into it:
import sys
import time
from collections import Counter

def main():
    input = sys.stdin.readline
    start = time.perf_counter()

    # Read count and the array of numbers
    n = int(input())
    nums = list(map(int, input().split()))
    # Counter builds the frequency map in one call
    freq = Counter(nums)

    # Print each value and its count
    for val, cnt in freq.items():
        print(f"{val}: {cnt}")

    end = time.perf_counter()
    print(f"Time: {(end - start) * 1000:.3f} ms", file=sys.stderr)

if __name__ == "__main__":
    main()

What does this code do?

  • Counter(nums) takes the entire list and returns a dictionary mapping each element to its count. One line replaces the entire for-loop you wrote in C++.
  • input = sys.stdin.readline reassigns the built-in to use the faster stdin reader. This matters when reading large inputs.
  • Run the Python solution against the same test file:
python python/frequency.py < test_freq.txt

You should see the same frequency counts as the C++ version. The order may differ, but the numbers and counts should match.

Output doesn't match the C++ version?

  • Both solutions use unordered containers, so the print order is not guaranteed to match. Compare the value-count pairs, not their order.
  • If you see an import error, make sure the first line says from collections import Counter with the correct capitalization.

Help me debug my frequency.py output.

Generate a large test input and race both solutions

Eight numbers run too fast to reveal any performance difference. To see how the languages compare under real contest pressure, you need a much larger input.

  • Create a file called generate_input.py in your project root. This utility will generate test inputs for all the problems in this project.
  • Paste the following code:
import random

def generate_frequency_input(n):
    # First line: count of numbers
    print(n)
    # Second line: n random integers between 1 and 1000
    print(" ".join(str(random.randint(1, 1000)) for _ in range(n)))

def generate_subarray_input(n, k):
    print(n, k)
    print(" ".join(str(random.randint(-1000, 1000)) for _ in range(n)))

def generate_adversarial_input(n, k):
    evil_prime = 107897
    print(n, k)
    print(" ".join(str(evil_prime * i for i in range(1, n + 1))))

if __name__ == "__main__":
    import sys
    mode = sys.argv[1] if len(sys.argv) > 1 else "freq"
    if mode == "freq":
        generate_frequency_input(1000000)
    elif mode == "subarray":
        generate_subarray_input(100000, 5)
    elif mode == "adversarial":
        generate_adversarial_input(100000, 5)

What does this script do?

This is your test data factory. It has multiple modes you will use throughout the project.

  • generate_frequency_input(1000000) produces 1 million random integers between 1 and 1000. That is enough to stress-test both solutions.
  • The other modes (subarray, adversarial) are for problems you will solve in later steps.
  • Save the file, then generate a large test input by running:
python generate_input.py freq > large_freq.txt

This creates large_freq.txt containing 1 million random integers. Now run both solutions against it.

  • Run the C++ solution against the large input:
./cpp/frequency < large_freq.txt > /dev/null

Why redirect to /dev/null?

Redirecting stdout to /dev/null discards the printed output so your terminal stays clean. The timing still prints to stderr, which is not redirected. On Windows, use NUL instead of /dev/null.

  • Now run the Python solution against the same large input:
python python/frequency.py < large_freq.txt > /dev/null
Observe the timing gap

Before you compare, take a moment to predict. How much faster do you think compiled C++ will be compared to Python on this 1-million-element input?

Look at the two timing outputs your terminal just printed. The C++ solution should finish in roughly 100-300 ms, while the Python solution takes roughly 500-1500 ms. The exact numbers depend on your machine, but C++ should be noticeably faster.

Why is C++ faster here?

C++ is compiled to native machine code with type-specialized containers. Python interprets each line at runtime and wraps every integer in an object with reference counting overhead. For contest problems with tight time limits (typically 1-2 seconds), this gap is often the difference between Accepted and Time Limit Exceeded.

✔️ Awesome, I've got everything!

Great. Make sure you have saved both cpp/frequency.cpp, python/frequency.py, and generate_input.py.

ⓧ I'd like to double check the full code

Here is the complete cpp/frequency.cpp:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto start = chrono::steady_clock::now();

    int n;
    cin >> n;
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        freq[x]++;
    }

    for (auto& [val, cnt] : freq) {
        cout << val << ": " << cnt << "\n";
    }

    auto end = chrono::steady_clock::now();
    chrono::duration<double, milli> elapsed = end - start;
    cerr << "Time: " << fixed << setprecision(3) << elapsed.count() << " ms" << endl;
    return 0;
}

Here is the complete python/frequency.py:

import sys
import time
from collections import Counter

def main():
    input = sys.stdin.readline
    start = time.perf_counter()

    n = int(input())
    nums = list(map(int, input().split()))
    freq = Counter(nums)

    for val, cnt in freq.items():
        print(f"{val}: {cnt}")

    end = time.perf_counter()
    print(f"Time: {(end - start) * 1000:.3f} ms", file=sys.stderr)

if __name__ == "__main__":
    main()

Here is the complete generate_input.py:

import random

def generate_frequency_input(n):
    print(n)
    print(" ".join(str(random.randint(1, 1000)) for _ in range(n)))

def generate_subarray_input(n, k):
    print(n, k)
    print(" ".join(str(random.randint(-1000, 1000)) for _ in range(n)))

def generate_adversarial_input(n, k):
    evil_prime = 107897
    print(n, k)
    print(" ".join(str(evil_prime * i for i in range(1, n + 1))))

if __name__ == "__main__":
    import sys
    mode = sys.argv[1] if len(sys.argv) > 1 else "freq"
    if mode == "freq":
        generate_frequency_input(1000000)
    elif mode == "subarray":
        generate_subarray_input(100000, 5)
    elif mode == "adversarial":
        generate_adversarial_input(100000, 5)

You have now seen the performance gap with your own eyes. Next up, you will tackle a harder problem where that gap becomes a real obstacle.

Solve Subarray Sum Equals K with Brute Force

Your frequency counter proved that hash maps are fast lookup machines. Now it is time to apply them to a real contest problem.

The problem is LeetCode 560: given an array of integers and a target k, count the number of contiguous subarrays whose elements sum to k. The obvious first approach is brute force: check every possible subarray. In this step, you will write that brute force, watch it work on a small input, then slam it into a large input and feel it choke.

In this step, get ready to:
  • Write an O(n²) brute force solution in C++ that checks every subarray.
  • Verify correctness on a small, hand-crafted test case.
  • Run the brute force on a large input and experience the performance wall firsthand.
Write the brute force C++ solution

The brute force idea is simple: for every starting index i, walk forward through every ending index j, accumulating the sum. Every time the running sum equals k, increment a counter. This checks all n*(n+1)/2 subarrays, giving O(n²) time.

  • Create a new file called cpp/subarray_sum_brute.cpp and add the input-reading portion:
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto start = chrono::steady_clock::now();

    // Read array size and target sum
    int n, k;
    cin >> n >> k;
    // Store all elements in a vector
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

What does this code do?

This is the same fast I/O template you used in your frequency counter. The input format is two numbers on the first line (n and k), followed by n integers on the second line.

  • Now add the brute force algorithm, output, and timing below the input-reading code:
    // Try every possible subarray with nested loops
    long long count = 0;
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum == k) count++;
        }
    }

    cout << count << "\n";

    auto end = chrono::steady_clock::now();
    chrono::duration<double, milli> elapsed = end - start;
    cerr << "Time: " << fixed << setprecision(3) << elapsed.count() << " ms" << endl;
    return 0;
}

What does this code do?

The outer loop picks a starting index i. The inner loop extends the subarray one element at a time, accumulating sum. Every time sum == k, that subarray qualifies.

Using long long for count and sum prevents overflow when numbers are large or the array is long.

  • Save cpp/subarray_sum_brute.cpp.
  • Create a small test input file to verify correctness by running:
echo "5 5" > test_subarray.txt
echo "1 2 3 -1 3" >> test_subarray.txt

What is this test case?

The array is [1, 2, 3, -1, 3] and the target sum is 5. The subarrays that sum to 5 are: [2, 3], [1, 2, 3, -1], and [3, -1, 3]. So the expected answer is 3.

  • Compile the brute force solution by running:
g++ -std=c++17 -O2 -o cpp/subarray_sum_brute cpp/subarray_sum_brute.cpp
  • Run it against your small test case:
./cpp/subarray_sum_brute < test_subarray.txt

You should see 3 printed to stdout, confirming the brute force logic is correct. The timing on stderr will show well under 1 ms for only 5 elements.

Seeing a different answer?

Double check that your test file has 5 5 on the first line (n=5, k=5) and 1 2 3 -1 3 on the second line. If you see a compiler error, make sure the closing braces of both for loops are present.

Help me debug my brute force solution

✔️ Awesome, I've got everything!

Great. Make sure you have saved cpp/subarray_sum_brute.cpp before moving on.

ⓧ I'd like to double check the full code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto start = chrono::steady_clock::now();

    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    long long count = 0;
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum == k) count++;
        }
    }

    cout << count << "\n";

    auto end = chrono::steady_clock::now();
    chrono::duration<double, milli> elapsed = end - start;
    cerr << "Time: " << fixed << setprecision(3) << elapsed.count() << " ms" << endl;
    return 0;
}
Hit the wall on large input

Five elements is trivial for any algorithm. The real question is: what happens when n grows to 100,000? An O(n²) solution would need to check around 5 billion subarray pairs.

  • Generate a large test input with 100,000 elements and a target sum of 5 by running:
python generate_input.py subarray > large_subarray.txt
  • Before you run the brute force against this large input, predict: how long do you think it will take to check all 5 billion subarray pairs, even in compiled C++?
  • Run the C++ brute force on the large input:
./cpp/subarray_sum_brute < large_subarray.txt

Watch the terminal hang for several seconds before producing a result. The timing output on stderr will show thousands of milliseconds. On a typical machine, expect something between 3,000 and 15,000 ms.

Why is it so slow?

With n=100,000, the nested loops run approximately 100,000 × 100,000 / 2 = 5 billion iterations. Even at hundreds of millions of operations per second, that takes multiple seconds.

Most contest judges set a 1-2 second time limit, so this solution would get a Time Limit Exceeded (TLE) verdict.

  • Now try the same approach in Python. Create a temporary file called python/subarray_sum_brute.py with this code:
import sys
import time

def main():
    input = sys.stdin.readline
    start = time.perf_counter()

    first_line = input().split()
    n, k = int(first_line[0]), int(first_line[1])
    nums = list(map(int, input().split()))

    # Brute force: check every subarray
    count = 0
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]
            if total == k:
                count += 1

    print(count)

    end = time.perf_counter()
    print(f"Time: {(end - start) * 1000:.3f} ms", file=sys.stderr)

if __name__ == "__main__":
    main()
  • Run the Python brute force on the same large input:
python python/subarray_sum_brute.py < large_subarray.txt

This will either hang for an extremely long time or you will need to interrupt it with Ctrl+C. Python's interpreted nested loops are roughly 50-100x slower than compiled C++. Where C++ took several seconds, Python would take minutes.

Why the massive gap?

C++ compiles the nested loop to native machine instructions with direct memory access. Python interprets each iteration through its runtime, checking types and managing references on every step. For tight numerical loops, this overhead dwarfs the actual computation.

In competitive programming, Python solutions often need a fundamentally better algorithm (lower time complexity) to pass within the time limit. Brute force that barely passes in C++ will almost always TLE in Python.

Python still running?

Press Ctrl+C to interrupt it. You have already proved the point: O(n²) is not viable at this scale, especially in Python.

What technique can reduce this from O(n²) to O(n)?

You have just experienced the exact wall that makes competitive programmers reach for smarter data structures. The brute force is correct, but hopelessly slow. In the next step, you will use a prefix sum combined with a hash map to solve this same problem in O(n) time.

Solve Subarray Sum Equals K with Prefix Sum + Hash Map

Your brute force hit a wall because it checks every pair of indices. There is a mathematical shortcut that eliminates the inner loop entirely.

The insight: if you keep a running sum (prefix sum) as you walk through the array, then any subarray summing to k corresponds to two prefix sums whose difference is k. A hash map that records how many times each prefix sum has appeared answers "how many valid subarrays end here?" in O(1).

In this step, get ready to:
  • Implement the O(n) prefix sum + hash map solution in C++.
  • Implement the same solution in Python using defaultdict.
  • Compare execution times against the brute force results on large input.
Implement the O(n) solution in C++

The key equation is: if prefix[j] - prefix[i] = k, then the subarray from index i+1 to j sums to k. You do not need to find which index i it was. You only need to know how many times a prefix sum of prefix - k has appeared so far.

  • Create a new file cpp/subarray_sum.cpp and paste the following code (the algorithm core with input reading):
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto start = chrono::steady_clock::now();

    // Read array size and target sum
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    // Prefix sum + hash map: count how often each prefix sum appeared
    unordered_map<long long, int> freq;
    freq[0] = 1;
    long long prefix = 0;
    long long count = 0;

    for (int i = 0; i < n; i++) {
        prefix += nums[i];
        if (freq.count(prefix - k)) {
            count += freq[prefix - k];
        }
        freq[prefix]++;
    }

What does this code do?

The freq map stores how many times each running prefix sum has appeared. Initializing freq[0] = 1 handles subarrays that start at index 0.

On each iteration, prefix += nums[i] extends the running sum. Then freq.count(prefix - k) checks whether any earlier prefix sum is exactly k less than the current one. Each match represents a valid subarray ending at this index.

The order matters: you check the map before inserting the current prefix. This avoids pairing a prefix sum with itself.

  • Now add the output and timing at the bottom of the same file:
    cout << count << "\n";

    auto end = chrono::steady_clock::now();
    chrono::duration<double, milli> elapsed = end - start;
    cerr << "Time: " << fixed << setprecision(3) << elapsed.count() << " ms" << endl;
    return 0;
}

Why use long long for prefix and count?

When elements range from -1000 to 1000 and the array can be large, the running sum can exceed the range of a 32-bit integer. Using long long for prefix and count prevents overflow on large inputs.

  • Save cpp/subarray_sum.cpp.
  • Compile it by running:
g++ -std=c++17 -O2 -o cpp/subarray_sum cpp/subarray_sum.cpp
  • Verify it works on a small test case by running:
echo "5 5
1 2 3 -1 4" | ./cpp/subarray_sum

You should see 2 printed (subarrays [2,3] and [1,2,3,-1] both sum to 5), plus a timing line on stderr.

Seeing a compile error?

Make sure the closing brace } of main() appears at the end of your file. The two code chunks above combine into a single complete file.

help me fix a compile error in my subarray_sum.cpp file

✔️ Awesome, I've got everything!

Great. Confirm you have saved cpp/subarray_sum.cpp and the compile produced no errors.

ⓧ I'd like to double check the full code

Your file is built from two chunks above. Scroll up and confirm both are present in order:

  • Chunk 1: from #include <bits/stdc++.h> through the closing } of the for loop (after freq[prefix]++;).
  • Chunk 2: from cout << count through the final } closing main().
Implement the same solution in Python

The algorithm is identical. Python uses defaultdict(int) from the collections module as the hash map, which returns 0 for missing keys.

  • Create python/subarray_sum.py and paste the following:
import sys
import time
from collections import defaultdict

def main():
    input = sys.stdin.readline
    start = time.perf_counter()

    first_line = input().split()
    n, k = int(first_line[0]), int(first_line[1])
    nums = list(map(int, input().split()))

    # Prefix sum + hash map: same logic as C++
    freq = defaultdict(int)
    freq[0] = 1
    prefix = 0
    count = 0

    for x in nums:
        prefix += x
        count += freq[prefix - k]
        freq[prefix] += 1

    print(count)

    end = time.perf_counter()
    print(f"Time: {(end - start) * 1000:.3f} ms", file=sys.stderr)

if __name__ == "__main__":
    main()

What is different from the C++ version?

Python's defaultdict(int) returns 0 for missing keys, so you can skip the if freq.count(...) check. The line count += freq[prefix - k] safely adds 0 if that prefix sum was never seen.

The input parsing splits the first line into n and k separately because sys.stdin.readline reads one line at a time.

  • Save python/subarray_sum.py.
  • Verify correctness on the same small test case by running:
echo "5 5
1 2 3 -1 4" | python3 python/subarray_sum.py

You should see 2 again, confirming both solutions agree.

Getting a different answer?

Make sure freq[0] = 1 appears before the loop. Without it, subarrays starting at index 0 are missed.

help me debug my Python subarray_sum solution

✔️ Awesome, I've got everything!

Great. Confirm you have saved python/subarray_sum.py.

ⓧ I'd like to double check the full code

import sys
import time
from collections import defaultdict

def main():
    input = sys.stdin.readline
    start = time.perf_counter()

    first_line = input().split()
    n, k = int(first_line[0]), int(first_line[1])
    nums = list(map(int, input().split()))

    freq = defaultdict(int)
    freq[0] = 1
    prefix = 0
    count = 0

    for x in nums:
        prefix += x
        count += freq[prefix - k]
        freq[prefix] += 1

    print(count)

    end = time.perf_counter()
    print(f"Time: {(end - start) * 1000:.3f} ms", file=sys.stderr)

if __name__ == "__main__":
    main()
Compare timing on large input

Time to see the payoff. You will run both optimized solutions against the same n=100,000 input that made brute force choke.

  • Generate the large test input by running:
python3 generate_input.py subarray > test_large.txt
  • Before you run the optimized solutions, think about this: the brute force took several seconds (C++) or was unusable (Python) on this same input. What do you expect the O(n) solution to do?
  • Run the C++ optimized solution:
./cpp/subarray_sum < test_large.txt
  • Run the Python optimized solution:
python3 python/subarray_sum.py < test_large.txt

Both produce the same count. The C++ solution finishes in well under 100ms. The Python solution finishes in under 1 second. Compare that to the brute force that took multiple seconds (C++) or could not finish (Python) on the same input.

Why is C++ faster here?

C++ is compiled to native machine code with typed containers. Each hash map lookup avoids the interpreter overhead that Python carries on every operation. This performance gap is exactly what causes Python solutions to receive TLE (Time Limit Exceeded) on competitive programming judges with strict time limits.

The algorithm is identical in both languages. The difference is purely in execution speed. In contests with tight time limits, the same O(n) logic passes in C++ but fails in Python.

Answers don't match between C++ and Python?

Both solutions should print the exact same count. If they differ, verify that both files initialize freq[0] = 1 and that the Python version uses long integers (it does this automatically, so check your input parsing instead).

help me figure out why my C++ and Python subarray sum solutions give different answers

You have just turned an unusable brute force into a solution that handles 100,000 elements in milliseconds. Next up, you will discover a scenario where unordered_map can actually become slower than map and learn how to defend against it.

Understand map vs unordered_map Tradeoffs

Your O(n) prefix sum solution is fast on random data. But on Codeforces, an opponent can craft inputs that deliberately exploit the default hash function of unordered_map, causing O(n²) collisions and turning your solution into a TLE.

In this step, you will experience this attack firsthand, then learn the standard defense used by competitive programmers worldwide.

In this step, get ready to:
  • Generate an adversarial input that exploits the default hash and observe your solution grind to a halt.
  • Write a custom hash function using splitmix64 that defends against the attack.
  • Understand the decision framework for choosing map vs unordered_map in contests.
Generate the adversarial input and watch your solution choke

Your generate_input.py already has an adversarial mode that creates 100,000 integers, all multiples of the prime 107897.

Why multiples of 107897?

In gcc 7+, unordered_map uses a prime-based rehash policy. The default std::hash for integers is the identity function. When you insert multiples of a prime that the map uses for bucket sizing, every key lands in the same bucket.

This degrades every operation from O(1) to O(n), giving O(n²) total insertion time. On Codeforces, opponents use this during the hacking phase to break solutions that rely on the default hash.

  • Generate the adversarial test input by running this command:
python generate_input.py adversarial > test_adversarial.txt
  • Confirm the file was created by running:
ls test_adversarial.txt

You should see test_adversarial.txt listed in the output.

Now, before you run your optimized solution against this input, make a prediction. Your solution is O(n) on random data. Do you think it will still be fast on this crafted input?

  • Compile your existing solution (if not already compiled) and run it against the adversarial input:
g++ -std=c++17 -O2 -o subarray_sum cpp/subarray_sum.cpp
./subarray_sum < test_adversarial.txt

Watch the terminal hang. Your "O(n)" solution is now taking multiple seconds on just 100,000 elements. The hash collisions turned every map operation into a linear scan through one giant bucket.

What should I see?

The program will eventually finish but the timing output will show several thousand milliseconds (or more). Compare this to the ~50ms you saw on random data of similar size. That slowdown is the O(n²) collision penalty in action.

Write the custom hash defense

The fix is a custom hash struct that uses the splitmix64 mixing function with a random seed. This produces well-distributed hash values that no adversary can predict.

  • Create a new file cpp/subarray_sum_safe.cpp and add the custom hash struct at the top:
#include <bits/stdc++.h>
using namespace std;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

What does this code do?

The splitmix64 function takes any integer and scrambles its bits through XOR shifts and multiplications. The magic constants produce an avalanche effect where changing one input bit flips roughly half the output bits.

The FIXED_RANDOM seed comes from chrono::steady_clock at program start. This makes the hash non-deterministic, so an adversary cannot predict which inputs will collide.

  • Below the custom_hash struct, add the main function:
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    auto start = chrono::steady_clock::now();

    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];

    unordered_map<long long, int, custom_hash> freq;
    freq[0] = 1;
    long long prefix = 0;
    long long count = 0;

    for (int i = 0; i < n; i++) {
        prefix += nums[i];
        if (freq.count(prefix - k)) {
            count += freq[prefix - k];
        }
        freq[prefix]++;
    }

    cout << count << "\n";

    auto end = chrono::steady_clock::now();
    chrono::duration<double, milli> elapsed = end - start;
    cerr << "Time: " << fixed << setprecision(3) << elapsed.count() << " ms" << endl;
    return 0;
}

What changed from the original?

The only difference from subarray_sum.cpp is the third template parameter: unordered_map<long long, int, custom_hash> instead of unordered_map<long long, int>. The algorithm is identical. The custom hash replaces the vulnerable default.

  • Save cpp/subarray_sum_safe.cpp.
  • Compile and run it against the same adversarial input by running:
g++ -std=c++17 -O2 -o subarray_sum_safe cpp/subarray_sum_safe.cpp
./subarray_sum_safe < test_adversarial.txt

This time the solution finishes in under 100ms. The custom hash distributes the adversarial keys across many buckets, restoring O(1) amortized performance.

Still seeing slow performance?

Make sure you included custom_hash as the third template parameter on the unordered_map declaration. If you wrote unordered_map<long long, int> without it, you are still using the default hash.

Also verify the custom_hash struct is defined before main() in the file. The compiler needs to see the struct before it is used as a template argument.

Help me debug my custom hash solution for unordered_map.

✔️ Awesome, I've got everything!

Great. Double check you have saved cpp/subarray_sum_safe.cpp with both the custom_hash struct and the main() function.

ⓧ I'd like to double check the full code

Your cpp/subarray_sum_safe.cpp should contain two sections in this order:

  • The #include, using namespace std, and the custom_hash struct (with splitmix64 and operator()).
  • The main() function, identical to subarray_sum.cpp except the map is declared as unordered_map<long long, int, custom_hash> freq.

Scroll up and confirm both code blocks are present and match what you pasted.

Know when to use each container in contests

You have now seen the full picture. Here is the decision framework that experienced competitive programmers use.

The contest decision framework

  • Use map as the safe default. It gives guaranteed O(n log n) per operation with no collision vulnerability. On Codeforces, this cannot be hacked.
  • Use unordered_map with a custom hash when you need O(1) amortized and the time limit is tight. The splitmix64 approach adds ~5 lines of boilerplate but makes your solution unhackable.
  • Never use unordered_map with the default hash in a contest where hacking is enabled. The adversary knows exactly how to break it.
  • Always benchmark before submitting if TLE is close. Run your solution against large random and adversarial inputs locally to confirm it fits within the time limit.

Keep the custom_hash as a snippet

Copy the custom_hash struct into your personal competitive programming template. You will use it in every contest where you reach for unordered_map.

You have now experienced the full arc: a solution that looks O(n) on paper can be blown up to O(n²) by an adversary who knows your hash function. The custom hash is your shield. Next up, you will put everything together in a Secret Mission that extends the prefix sum pattern to divisibility problems.

Secret mission

Solve Subarray Sums Divisible by K

You have mastered the prefix sum + hash map technique for exact target sums. Now apply a modulo variation to solve LeetCode 974, where you count subarrays whose sum is divisible by k. This introduces a subtle trap: C++ and Python handle negative modulo differently, and your solution must account for it.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your files for future practice or delete them entirely.

Resources you used:

  • Your project folder on the Desktop (containing the cpp/ and python/ directories, plus generate_input.py).
  • Any generated test input files (created by running generate_input.py).
  • Compiled binary files in the cpp/ directory.

Keep everything running

No action needed. Choose this if you plan to keep practicing competitive programming problems using this workspace.

  • Your files sit on your Desktop and use minimal disk space.
  • Add new problem files to the cpp/ and python/ directories as you tackle more problems.
  • Reuse template.cpp and template.py as starting points for new solutions.
  • Reuse generate_input.py to create large test cases for future problems.

Pause - I'll come back to this later

Since this is a local-only project with no running processes, there is nothing to pause. Your files remain on disk until you decide to return or delete them.

  • No servers or background processes are running from this project.
  • To free a small amount of disk space, delete the generated test input files (they can be regenerated later).

Delete - I don't want to use this again

Remove all project files from your system. This deletes all your solutions, templates, and generated inputs permanently.

  • Delete the project folder by running the command for your operating system.

On macOS or Linux:

cd ~/Desktop
rm -rf cp-hashmaps

On Windows:

cd ~\Desktop
rmdir /s /q cp-hashmaps
  • Confirm the folder is gone by running ls (macOS/Linux) or dir (Windows) on your Desktop.

Nice Work!

Nice Work!

Nice work! You just solved a classic competitive programming problem in two languages, measured the performance difference firsthand, and learned a critical contest trap that catches even experienced competitors.

You've learned how to:

  • Solve LeetCode 560 (Subarray Sum Equals K) using the prefix sum + hash map pattern in both C++ and Python, reducing an O(n²) brute force to O(n).
  • Measure and compare the performance gap between compiled C++ and interpreted Python on large inputs, understanding why Python can TLE on strict contest time limits.
  • Defend against the unordered_map anti-hash attack using a splitmix64 custom hash, and apply the decision framework for choosing between map and unordered_map in contests.
  • Secret Mission: Solved LeetCode 974 (Subarray Sums Divisible by K) with modulo prefix sums and handled the negative modulo edge case in C++.

Ready to quiz yourself?