What is the brute force approach and complexity for Building Bridges?

Sort by north, then try keep or skip for each bridge; keep a bridge only if its south end is not lower than the last one kept with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Building Bridges?

Sort by north; keep tails[k] = smallest south end of a run of k + 1 bridges; binary search each new south end with optimal time complexity O(N log N) and space complexity O(N).

How do you identify the pattern for Building Bridges?

Look for key signals in the prompt: "cities paired by index" indicates Each bridge is one pair (north, south). Sort the pairs as a whole. Do not sort the two lists separately.; "no two bridges cross" indicates After sorting by north, the south ends must never go down. That is a rule on one list, so the 2D problem becomes a 1D one.; "maximum number of bridges" indicates We want the longest valid run, so the answer is a length, which `tails` gives directly..

Building Bridges

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelDP — LIS, 2D / envelopes (sort by one side, then a non-decreasing run on the other)

Complexity:O(2^N)→O(N log N)

Key Insight

Sort by north (ties by south). Keep tails[k] = the smallest south end that finishes a run of k + 1 bridges. For a new bridge with south end s, find the first tail bigger than s with binary search. Replace that tail with s. If no tail is bigger than s, append s. The answer is the number of tails.

Core Validity Invariant

A bridge with south end s can extend a run only when the run's last south end is not higher than s, so the longest run it can extend is the one that the upper_bound search finds.

Problem

Picture a river with cities on both banks. Each city on the north bank is paired with one city on the south bank by index: north[i] can only be joined to south[i]. A bridge joins north[i] → south[i].

You want as many bridges as possible, with no two bridges crossing. Two bridges cross when one starts further left on the north bank but ends further right on the south bank. Bridges that start or end at the same x-coordinate do not cross.

Return the largest number of bridges you can build.

Input

Two lists of the same length n: north and south. Bridge i joins north[i] to south[i].

Output

The largest number of bridges that can be built with no crossing.

Example 1

Input: north = [6, 4, 2, 1], south = [2, 3, 6, 5]

Output: 2

The bridges 2 → 6 and 1 → 5 do not cross, and they can be built together. No set of three bridges works without a crossing.

Example 2

Input: north = [8, 1, 4, 3, 5, 2, 6, 7], south = [1, 2, 3, 4, 5, 6, 7, 8]

Output: 5

The bridges 1 → 2, 3 → 4, 5 → 5, 6 → 7 and 7 → 8 all go up on both banks, so none of them cross.

Constraints

• Both lists have the same length `n`. No other limits are given.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Two bridges cross when their order is flipped on the two banks. Which order do I need to keep on both banks?
2.
If I sort the bridges by their north end, what must the south ends do so that no two bridges cross?
3.
Does the order of the input lists matter for the answer? What happens if I look at the south ends in the order they were given?
4.
Can two bridges share the same north x-coordinate? If they do, what order should their south ends be in?
5.
This looks like the Longest Increasing Subsequence. What changes about the word 'increasing' here?

Brute force approach

Idea

Sort the bridges by north, ties by south. Go through them in order. For each bridge, choose to skip it, or to keep it when its south end is not lower than the south end of the last bridge kept. Try both choices every time and keep the bigger count.

Thinking process

1
Take north = [6, 4, 2, 1] and south = [2, 3, 6, 5]. Sorted by north, the bridges are 1 → 5, 2 → 6, 4 → 3 and 6 → 2.
2
Keep 1 → 5. The last south end is 5. Next, 2 → 6: its south end 6 is not lower than 5, so keep it too. Now the last south end is 6, and 4 → 3 and 6 → 2 are both lower, so both are skipped. Count: 2.
3
Skip 1 → 5 instead. Keep 2 → 6 and both later bridges are lower than 6, so the count is 1. Keep 4 → 3 and the last bridge 6 → 2 is still lower than 3, so the count is 1 again. Without 1 → 5 the best is 1.
4
The better of the two choices for 1 → 5 is 2. The recursion finds this by trying every keep/skip pattern.
5
Many keep/skip patterns end in the same 'next bridge, last south end' state, and the brute force works each of them out again.

Visual

Each circle is one call: i = the next pair to decide, and the note is the last south end kept. Blue = the calls now open. Orange = a state (next pair, last south end) already solved on another branch, which brute force works out again.

Brute force: keep or skip each pairpairs (north, south) = (6,2), (4,3), (2,6), (1,5)step 1/31

calls

pairs

1→5

2→6

4→3

6→2

▲i

State

next pair i: 0
last south kept: none
calls: 1
repeated calls: 0

Pair 0: 1→5

Decide pair 1→5: skip it, or keep it when 5 is not lower than none.

Code & Implementation

brute.cpp

class Solution {
    // go(i, last): the most bridges we can still add from pairs[i..], when the last bridge built ends at south `last`.
    // Every pair is either skipped, or built if it does not cross the last bridge.
    int go(vector<pair<int, int>>& pairs, int i, int last) {
        if (i == (int)pairs.size()) return 0;
        int best = go(pairs, i + 1, last);                    // skip pairs[i]
        if (pairs[i].second >= last)                          // its south city is not left of the last bridge: no crossing
            best = max(best, 1 + go(pairs, i + 1, pairs[i].second));
        return best;
    }

public:
    int maxBridges(vector<pair<int, int>>& pairs) {
        sort(pairs.begin(), pairs.end());                     // by north, then by south
        return go(pairs, 0, INT_MIN);
    }
};

Complexity

Time O(2^N)Space O(N)

Each bridge is kept or skipped, so there are at most 2^N paths through the decisions. The sort costs O(N log N), which is smaller. The space is the recursion depth, which is N.

Better approach

Why brute force is slow

The brute force keeps asking for the best result from the same point again and again. Each keep/skip path ends in a 'next bridge, last south end' state, and the same state is reached by several paths.

What repeated work are we doing?

On the example, the state 'next bridge is 4 → 3, last south end is 6' is reached twice: once after keeping 1 → 5 and 2 → 6, and once after skipping 1 → 5 and keeping 2 → 6. The brute force solves it both times.

What information can we reuse?

best[i] is one number for each bridge. It depends only on the earlier bridges, so each one is worked out once, and the answer is the largest of them.

New approach

Idea

Sort by north. Let best[i] be the most bridges you can build when bridge i is the last one. An earlier bridge j can come before i only when south[j] ≤ south[i]. So best[i] = 1 + max best[j] over those earlier j, or 1 when none fits.

Thinking process

1
Sorted bridges: 1 → 5, 2 → 6, 4 → 3, 6 → 2. Their south ends are 5, 6, 3 and 2.
2
best[0] = 1: the bridge 1 → 5 on its own.
3
best[1]: bridge 2 → 6 has south end 6. The earlier south end 5 is not higher, so it can come first: best[1] = best[0] + 1 = 2.
4
best[2]: bridge 4 → 3 has south end 3. The earlier south ends 5 and 6 are both higher, so nothing can come before it: best[2] = 1.
5
best[3]: bridge 6 → 2 has south end 2. Nothing earlier is lower than 2, so best[3] = 1. The answer is the largest value: max(1, 2, 1, 1) = 2.

Code & Implementation

better.cpp

class Solution {
public:
    int maxBridges(vector<pair<int, int>>& pairs) {
        if (pairs.empty()) return 0;
        sort(pairs.begin(), pairs.end());                     // by north, then by south
        int n = pairs.size();
        vector<int> best(n, 1);                               // best[i] = most bridges in a chain that ends at pairs[i]
        for (int i = 1; i < n; i++)
            for (int j = 0; j < i; j++)
                // north[j] <= north[i] already (sorted). Equal souths are fine: the bridges do not cross.
                if (pairs[j].second <= pairs[i].second)
                    best[i] = max(best[i], best[j] + 1);
        return *max_element(best.begin(), best.end());
    }
};

Complexity

Time O(N²)Space O(N)

Each bridge looks back at the earlier ones: about N²/2 comparisons. The sort is O(N log N), which is smaller. The array stores one value per bridge.

Optimized approach

Idea

Start from brute force

The brute force decides keep or skip for each bridge, and it only needs the south end of the last bridge it kept. Many different paths end with the same last south end, so the same work is repeated.

Find the repeated work

For every run length, the brute force only needs the smallest south end that can finish a run of that length, not every path. Keeping just that value per length removes the repeated work.

Define the state — what variables do I need?

tails[k]: The smallest south end that can finish a run of k + 1 bridges, among the bridges seen so far. `tails` is always sorted from low to high.
s: The south end of the bridge being added now.
pos: The first index where `tails[pos] > s`, found by binary search. It means `pos` tails are not higher than `s`, so `s` can extend a run of `pos` bridges.

Define validity

A bridge with south end s can extend a run only when the run's last south end is not higher than s, so the longest run it can extend is the one that the upper_bound search finds.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

tails = []

No bridges are seen yet, so no run exists.

Each bridge, in sorted order

pos = upper_bound(tails, s)

pos is the first tail bigger than s. The tail just before it is not bigger than s, so the bridge can extend that run.

pos is past the end of tails

append s

No tail is bigger than s, so s extends the longest run. That makes a new longest run.

pos is inside tails

tails[pos] = s

A run of length pos + 1 can now end at s, which is lower than before. A lower end leaves more room for the bridges that come later, and the number of tails does not change.

What does the current window add to the answer?

After each bridge, tails.size() is the longest run of bridges seen so far. After the last bridge, it is the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    int maxBridges(vector<pair<int, int>>& pairs) {
        sort(pairs.begin(), pairs.end());                     // by north, then by south
        // tails[k] = the smallest south value that ends a chain of k + 1 bridges so far.
        // tails is always non-decreasing, so it can be searched with binary search.
        vector<int> tails;
        for (const auto& p : pairs) {
            // upper_bound: the first tail that is strictly bigger than p.second.
            // An equal south value may follow a bridge, so equal values must not be pushed out of the way.
            auto it = upper_bound(tails.begin(), tails.end(), p.second);
            if (it == tails.end()) tails.push_back(p.second);   // extends the longest chain
            else *it = p.second;                                // a chain of this length can now end lower
        }
        return (int)tails.size();
    }
};

Complexity

Time O(N log N)Space O(N)

The sort is O(N log N). Each bridge does one binary search over tails, which holds at most N values, so the loop is also O(N log N). tails is not itself a valid set of bridges, so only its length is the answer.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Sort by north, then try keep or skip for each bridge; keep a bridge only if its south end is not lower than the last one kept	O(2^N)	O(N)
Better	dp[i] = most bridges in a run that ends at bridge i; check every earlier bridge whose south end is not higher	O(N²)	O(N)
Optimal	Sort by north; keep tails[k] = smallest south end of a run of k + 1 bridges; binary search each new south end	O(N log N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“cities paired by index”Each bridge is one pair (north, south). Sort the pairs as a whole. Do not sort the two lists separately.
“no two bridges cross”After sorting by north, the south ends must never go down. That is a rule on one list, so the 2D problem becomes a 1D one.
“maximum number of bridges”We want the longest valid run, so the answer is a length, which `tails` gives directly.

Sort by one side (north, ties by south)+longest run where the other side never goes down+maximum count→DP — LIS, 2D / envelopes (sort by one side, then a non-decreasing run on the other)

The sort turns a 2D rule into a 1D one: after sorting by north, bridges are valid exactly when their south ends never go down. Ties on north are sorted by south, so bridges that share a north end can all be kept. The key difference from Classic LIS is that equal values are allowed, so the search uses upper_bound. Best Team With No Conflicts uses the same sort-then-run idea, but adds a score to each run.

Don't make this mistake

Pattern confusion: running the LIS on the list in input order

✗ // no sort: walk the pairs in the order they were given for (auto& p : pairs) { /* tails + upper_bound on p.second */ }

✓ sort(pairs.begin(), pairs.end()); // by north first, then the run on south

The input order is not the order of the north ends, so a run of south values can jump across bridges that cross. On the first example the south values in input order are 2, 3, 6, 5. The run 2, 3, 6 has length 3, so this code returns 3. But the bridges 6 → 2 and 2 → 6 cross each other, so the right answer is 2.

Equal north ends sorted the wrong way

✗ sort(pairs.begin(), pairs.end(), [](auto& a, auto& b) { return a.first != b.first ? a.first < b.first : a.second > b.second; });

✓ sort(pairs.begin(), pairs.end()); // ties on north: smaller south first

Two bridges that start at the same north end do not cross, so both can be kept. Sorting ties with the south end descending puts the bigger south first, and the run can then keep only one of them. On north = [3, 3] and south = [7, 2] the right answer is 2, but this code returns 1.

Strict comparison: lower_bound instead of upper_bound

✗ auto it = lower_bound(tails.begin(), tails.end(), p.second);

✓ auto it = upper_bound(tails.begin(), tails.end(), p.second);

Two bridges that end at the same south city do not cross, so the second can follow the first. On north = [1, 2] and south = [5, 5], the right answer is 2. lower_bound replaces the 5 instead of adding a new run, so it returns 1.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Longest Increasing Subsequence translate into production architectures and low-level memory mechanics.

LLD Architecture