Problem 41.5 · Concurrency-Aware Data StructuresEasy

Parallel Array Sum

PatternCombine Structures to Design Divide and Conquer

What it teaches: Split work into chunks, run them on a thread pool, and combine the Futures.

In plain words

You need to add up a long list of numbers and have a few helpers. Cut the list into equal pieces, give each helper one piece to add up at the same time, then add their answers together. Each helper keeps its own subtotal, so they never fight over one shared total.

Return the total sum. Example: nums = [1..10], threads = 3 → 55.

The problem

Return the sum of nums (as a long) computed with threads worker threads, each summing one contiguous chunk.

Example 1

Input: nums = [1..10], threads = 3
Output: 55

Constraints

0 ≤ n ≤ 10⁶
1 ≤ threads ≤ 16

Pattern clues in the wording

→ Independent pieces of work
→ Combine partial results

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;
import java.util.concurrent.*;

class Solution {
    public long parallelSum(int[] nums, int threads) throws Exception {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,2,3,4,5,6,7,8,9,10] threads = 3	55
2	nums = [] threads = 2	0
3	nums = [2147483647,2147483647] threads = 2	4294967294

From slow to fast

Approaches

1. ExecutorService + Futures · O(n / threads) ideal wall time 2. Parallel stream · O(n / cores)

ExecutorService + Futures

Time O(n / threads) ideal wall time Space O(threads)

Fixed pool; submit one Callable per chunk; sum the results; shut the pool down in finally.

▶ Dry run: Chunks to a thread pool, then join the futuresnums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], threads = 3

state(vars)

chunk: ceil(10 / 3) = 4

Step 1/5Chunk size = (10 + 3 − 1) / 3 = 4, so the pieces are indexes 0–3, 4–7 and 8–9.

Approach 1

import java.util.*;
import java.util.concurrent.*;

class Solution {
    public long parallelSum(int[] nums, int threads) throws Exception {
        ExecutorService pool = Executors.newFixedThreadPool(threads);
        try {
            int n = nums.length, chunk = Math.max(1, (n + threads - 1) / threads);
            List<Future<Long>> parts = new ArrayList<>();
            for (int start = 0; start < n; start += chunk) {
                int s = start, e = Math.min(n, start + chunk);
                parts.add(pool.submit(() -> {
                    long t = 0;
                    for (int i = s; i < e; i++) t += nums[i];
                    return t;
                }));
            }
            long total = 0;
            for (Future<Long> f : parts) total += f.get();
            return total;
        } finally {
            pool.shutdown();
        }
    }
}

Verdict: The basic fork-join shape.

Parallel stream

Time O(n / cores) Space O(1)

Arrays.stream(nums).parallel().asLongStream().sum() uses the common ForkJoinPool.

Approach 2

import java.util.Arrays;

class Solution {
    public long parallelSum(int[] nums, int threads) {
        return Arrays.stream(nums).parallel().asLongStream().sum();
    }
}

Verdict: One line; less control over the pool.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty array
More threads than elements
Sum beyond int

Mistakes people make

Summing into a shared long from every thread without synchronisation.

Interview

Follow-up questions

When does parallelism not help?