Start learning free

LESSON 193 OF 348 · NESTED LOOPS & BRUTE FORCE

Pair Count in TypeScript: O(n^2) with Nested Loops

Practice O(n²) Read the full explanation

Given two positive integers n and sum, count the number of different pairs of integers (x, y) such that 1 <= x, y <= n and x + y equals sum

Example:

Input: n = 7, sum = 6
Output: 3
Explanation: There are 3 valid pairs: (1, 5), (2, 4), (3, 3).
Note that pairs such as (1, 5) and (5, 1) are not considered different.

Note:

Your algorithm should run in O(n^2) time and use O(1) space.

Hints:

Let's come up with a brute force approach. Brute force tries each and every candidate to our solution. For this problem, the candidates are all the pairs of numbers (x, y) such that 1 <= x <= y <= n. How can we try out all these pairs?

Using two nested for loops! The first loop will try out each possible x between 1 and n. The second loop will be written inside the first one and will try out each possible y between x and n.

for each x : 1 -> n:
	for each y : x -> n:

What should be written inside these loops?

Inside the loops we should check if the pair (x, y) is a solution, e.g. if x + y == sum. If so, we should add 1 to the answer. But where do we store the answer? We'll need a variable for that. Let's name it result.

result = 0
for each x : 1 -> n:
	for each y : x -> n:
		if x + y == sum:
			result += 1
return result

STEP 1 OF 5

Guided

Ctrl + Enter to check

TYPESCRIPT · NESTED LOOPS & BRUTE FORCE

Pair Count in TypeScript, explained

Problem overview

The method countPairs receives two positive integers, n and sum. It returns how many different pairs of integers (x, y) satisfy 1 <= x, y <= n and x + y = sum.

For n = 7 and sum = 6 the answer is 3: the pairs are (1, 5), (2, 4) and (3, 3). The pair (5, 1) is the same pair as (1, 5), so it isn't counted again, and a pair may use the same number twice, as (3, 3) does.

Approach: try every candidate pair

The statement asks for O(n^2) time and O(1) space, which signals a brute-force solution: generate every candidate pair, test it, and count the ones that work. Two nested loops do exactly that. The outer loop picks x, the inner loop picks y, and every combination gets tested once.

The only subtlety is not counting (1, 5) and (5, 1) separately. The fix is to make y start at x rather than at 1. Then every pair is generated with its smaller number first, so each unordered pair appears exactly once. The case y = x is included, which is what lets (3, 3) be counted.

Tracing the example

With n = 7 and sum = 6, the loops visit the pairs in this order: (1, 1), (1, 2), ... (1, 7), then (2, 2), (2, 3), ... (2, 7), and so on up to (7, 7). The sum equals 6 only at (1, 5), at (2, 4) and at (3, 3). From i = 4 onward the smallest possible sum is i + i, which is at least 8, so nothing else can match. The counter ends at 3.

The loops keep running through those later rows anyway, because the method has no way of knowing it could stop. Stopping early would be an optimisation, but the lesson's budget of O(n^2) already allows the plain version.

The nested loops are not the only way. Once x is chosen, y has no freedom: it must equal sum - x. A single loop over x can check whether that y is at least x and at most n, which gives O(n) time. This lesson practises nested loops, so it tests every pair instead.

Step by step

Declare result. It is a let variable typed number and starts at 0, because nothing has been found yet.
Loop over the first number. The index i goes from 1 to n inclusive, so the condition is i <= n. Unlike array indexes, these values start at 1.
Loop over the second number. Inside the first loop, j starts at i and runs while j <= n.
Test the pair. If i + j === sum, add one to result. Each match is a distinct pair, so each one adds exactly 1.
Return result after both loops end.

The solution in TypeScript

class Solution {
    countPairs(n: number, sum: number): number {
        let result: number = 0;
        for (let i = 1; i <= n; i++) {
            for (let j = i; j <= n; j++) {
                if (i + j === sum) {
                    result++;
                }
            }
        }
        return result;
    }
}

A few TypeScript details:

The annotation on result is optional, since TypeScript infers number from the 0. It is written here to make the type visible. Annotations are erased when the code is compiled, so they have no effect when the program runs.
There is one numeric type. number covers integers and decimals alike, so there is no separate int. For these inputs it makes no difference, because integers up to 2^53 are represented exactly.
=== compares without converting types. It is the usual choice in TypeScript. i + j is a number and so is sum, so the comparison does what you expect.
result++ adds 1 to the variable. It is the short form of result = result + 1.

Complexity

Time: O(n^2). For i = 1 the inner loop runs n times, for i = 2 it runs n - 1 times, and so on down to 1. That adds up to n(n + 1) / 2 tests, which grows like n^2.

Space: O(1). The method uses only result and the two loop indexes, no matter how large n is.

Edge cases and common mistakes

Starting j at 1. That counts ordered pairs, so (1, 5) and (5, 1) both count. For n = 7, sum = 6 it would return 5 instead of 3.
Starting j at i + 1. That skips the pairs where both numbers are equal. The example would return 2 and miss (3, 3).
Using < instead of <=. Then n itself is never tried. With n = 1 and sum = 2 the answer should be 1, for (1, 1).
Large inputs. The body runs about n^2 / 2 times, so n = 100000 means roughly five billion tests, far too slow in practice. The quadratic budget fits the small inputs of this lesson, and the single-loop idea above is the way to scale.
A sum that is too large or too small. The largest possible sum is 2 * n. For n = 3 and sum = 100 no pair matches and the result stays 0.

Testing

n = 7, sum = 6 gives 3.
n = 1, sum = 2 gives 1.
n = 4, sum = 2 gives 1.
n = 5, sum = 3 gives 1.
n = 3, sum = 100 gives 0.

Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free