LeetCode Problem 3413

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Greedy, Sliding Window, Sorting, Prefix Sum

Solution

LeetCode 3413 - Maximum Coins From K Consecutive Bags

Problem Understanding

We are given several non-overlapping segments on a number line. Each segment [l, r, c] means that every bag at positions l, l+1, ..., r contains exactly c coins.

All positions not covered by any segment contain 0 coins.

The goal is to choose a contiguous block of exactly k consecutive bag positions and maximize the total number of coins collected from those bags.

For example, if a segment is [5, 6, 4], then position 5 contains 4 coins and position 6 also contains 4 coins. Any position outside all segments contributes 0.

A direct representation of the number line is impossible because coordinates can be as large as 10^9. Even though there are only at most 10^5 segments, each segment may span billions of positions.

The important observation is that the coin distribution is piecewise constant. The value only changes at segment boundaries. Therefore, instead of thinking about individual bags, we must reason about intervals.

The constraints tell us several important things:

• There may be up to 10^5 segments.
• Coordinates can be as large as 10^9.
• The total covered length may be far larger than memory limits.
• Any solution that iterates over individual positions is impossible.
• Since segments are non-overlapping, sorting and interval processing become attractive.

Important edge cases include:

• A window may lie completely inside a single segment.
• A window may partially overlap several segments.
• The optimal window may start or end in a gap where bags contain zero coins.
• k may be much larger than any individual segment length.
• Segments may be extremely far apart, creating huge stretches of zeros.

Approaches

Brute Force

The most direct idea is to explicitly construct the number line and evaluate every possible interval of length k.

For every starting position x, we would compute the sum over [x, x+k-1] and keep the maximum.

This is clearly correct because every possible window is examined.

Unfortunately, coordinates reach 10^9, so even storing the number line is impossible. The number of candidate windows is also enormous. Therefore this approach is completely infeasible.

Key Observation

The coin value changes only at segment boundaries.

Suppose we define:

• f(x) = coins at position x

Then f(x) is a piecewise constant function.

We want:

$$\max_s \sum_{x=s}^{s+k-1} f(x)$$

Since the function only changes at interval boundaries, an optimal window can always be shifted until either:

• its left endpoint aligns with a segment start, or
• its right endpoint aligns with a segment end.

If neither endpoint touches such a boundary, the entire window lies inside regions where the density is unchanged, and sliding the window slightly does not alter the total.

Therefore it is sufficient to examine windows whose:

• left edge equals some segment start, and
• right edge equals some segment end.

This reduces the infinite search space to only O(n) candidate anchor positions.

We can efficiently evaluate these candidates using a two-pointer sliding window over the sorted segments.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(10^9) or worse	O(10^9)	Impossible due to coordinate size
Optimal	O(n log n)	O(1) extra	Sort intervals and use interval sliding windows

Algorithm Walkthrough

The core idea is to create a helper function that computes the best window whose left boundary coincides with some segment start.

Later we run the same logic in reverse to handle windows whose right boundary coincides with some segment end.

1. Sort the segments

Sort all segments by their starting coordinate.

This allows us to process them from left to right and maintain a sliding interval efficiently.

2. Consider windows anchored at segment starts

For every segment start l:

• The window becomes [l, l+k-1].
• We want the total coins inside this interval.

Maintain:

• a pointer j
• a running sum of fully covered segments

As the window expands, move j forward while entire segments fit inside the current window.

3. Add fully covered segments

For each fully covered segment:

(length of segment) × (coins per position)

is added to the running sum.

Because each segment enters and leaves the sliding structure at most once, the total work remains linear.

4. Handle the partially covered segment

The window may end inside one segment.

If so, compute the overlap length:

overlap = window_end - segment_start + 1

and add:

overlap × coin_value

This gives the exact value of the current window.

5. Slide to the next start position

When moving from one segment start to the next:

• remove the contribution of the segment that is no longer fully inside the active structure
• continue advancing the right pointer as necessary

This is the standard two-pointer technique.

6. Repeat symmetrically

The previous pass only checks windows whose left endpoint equals a segment start.

However, an optimal window might instead be characterized by its right endpoint touching a segment end.

To capture those cases:

• mirror all coordinates
• run the same procedure again
• take the maximum of both passes

7. Return the largest value found

The answer is the maximum value observed across both scans.

Why it works

Any interval of length k can be continuously shifted left or right until one of its boundaries touches a segment boundary without decreasing its value. This follows from the fact that coin density is constant between boundaries.

Therefore an optimal solution must have either:

• left endpoint at a segment start, or
• right endpoint at a segment end.

The first scan checks all windows of the first type. The mirrored scan checks all windows of the second type. Since every optimal window belongs to at least one of these categories, taking the maximum over both scans yields the global optimum.

Python Solution

from typing import List

class Solution:
    def maximumCoins(self, coins: List[List[int]], k: int) -> int:
        def solve(intervals: List[List[int]]) -> int:
            intervals.sort()

            n = len(intervals)
            ans = 0

            current = 0
            j = 0

            for i in range(n):
                left = intervals[i][0]
                right = left + k - 1

                while j < n and intervals[j][1] <= right:
                    l, r, c = intervals[j]
                    current += (r - l + 1) * c
                    j += 1

                total = current

                if j < n and intervals[j][0] <= right:
                    l, r, c = intervals[j]
                    overlap = right - l + 1
                    total += overlap * c

                ans = max(ans, total)

                l, r, c = intervals[i]
                current -= (r - l + 1) * c

            return ans

        ans = solve([seg[:] for seg in coins])

        mirrored = []
        for l, r, c in coins:
            mirrored.append([-r, -l, c])

        ans = max(ans, solve(mirrored))

        return ans

Implementation Explanation

The helper function solve() assumes we only need to consider windows whose left boundary equals a segment start.

The intervals are sorted by starting coordinate. The pointer j identifies the first segment that is not fully covered by the current window.

The variable current stores the contribution of all segments completely contained inside the window.

For every candidate start position:

• compute the window end,
• extend j while segments remain fully covered,
• add a possible partial overlap from the next segment,
• update the answer.

After processing a start position, the contribution of that segment is removed from current because future windows no longer fully contain it.

To handle windows characterized by a right endpoint touching a segment end, coordinates are mirrored:

[l, r] -> [-r, -l]

Running the same algorithm on the mirrored intervals effectively evaluates the complementary family of optimal windows.

The final answer is the maximum of the two passes.

Go Solution

package main

import "sort"

func maximumCoins(coins [][]int, k int) int64 {
	solve := func(intervals [][]int) int64 {
		sort.Slice(intervals, func(i, j int) bool {
			return intervals[i][0] < intervals[j][0]
		})

		n := len(intervals)
		var ans int64
		var current int64

		j := 0

		for i := 0; i < n; i++ {
			left := intervals[i][0]
			right := left + k - 1

			for j < n && intervals[j][1] <= right {
				l := intervals[j][0]
				r := intervals[j][1]
				c := intervals[j][2]

				current += int64(r-l+1) * int64(c)
				j++
			}

			total := current

			if j < n && intervals[j][0] <= right {
				l := intervals[j][0]
				c := intervals[j][2]

				overlap := right - l + 1
				total += int64(overlap) * int64(c)
			}

			if total > ans {
				ans = total
			}

			l := intervals[i][0]
			r := intervals[i][1]
			c := intervals[i][2]

			current -= int64(r-l+1) * int64(c)
		}

		return ans
	}

	copy1 := make([][]int, len(coins))
	for i := range coins {
		copy1[i] = []int{coins[i][0], coins[i][1], coins[i][2]}
	}

	ans := solve(copy1)

	mirrored := make([][]int, len(coins))
	for i, seg := range coins {
		l, r, c := seg[0], seg[1], seg[2]
		mirrored[i] = []int{-r, -l, c}
	}

	other := solve(mirrored)

	if other > ans {
		ans = other
	}

	return ans
}

Go-Specific Notes

The result may exceed the range of a 32-bit integer because:

• segment length can be up to 10^9
• coin value can be up to 1000

Therefore all accumulated sums use int64.

The logic is otherwise identical to the Python implementation. Slices are copied before sorting so that subsequent passes do not interfere with each other.

Worked Examples

Example 1

Input:

coins = [[8,10,1],[1,3,2],[5,6,4]]
k = 4

After sorting:

Segment	Coins
[1,3]	2
[5,6]	4
[8,10]	1

Consider start position 1.

Window:

[1,4]

Contribution:

Range	Coins
[1,3]	3 × 2 = 6
[4]	0

Total = 6

Consider start position 5.

Window:

[5,8]

Contribution:

Range	Coins
[5,6]	2 × 4 = 8
[7]	0
[8]	1

Total = 9

The mirrored pass examines windows ending at interval boundaries.

Window:

[3,6]

contains:

2 + 0 + 4 + 4 = 10

Maximum = 10

Example 2

Input:

coins = [[1,10,3]]
k = 2

Window:

[1,2]

Contribution:

3 + 3 = 6

Any other length-2 window inside the segment also gives 6.

Answer = 6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates, two-pointer scan is linear
Space	O(1) extra, excluding sorting	Only a few variables and pointers are maintained

The intervals are sorted once per pass. Each pass costs O(n log n) due to sorting and O(n) for the sliding-window traversal. Since we perform two passes, the asymptotic complexity remains O(n log n).

Test Cases

sol = Solution()

assert sol.maximumCoins([[8,10,1],[1,3,2],[5,6,4]], 4) == 10  # example 1

assert sol.maximumCoins([[1,10,3]], 2) == 6  # example 2

assert sol.maximumCoins([[1,5,2]], 5) == 10  # exact segment length

assert sol.maximumCoins([[1,5,2]], 3) == 6  # window inside segment

assert sol.maximumCoins([[1,2,5],[10,11,7]], 2) == 14  # choose richer segment

assert sol.maximumCoins([[1,2,5],[4,5,5]], 4) == 20  # span gap

assert sol.maximumCoins([[1,1,10]], 1) == 10  # single position

assert sol.maximumCoins([[1,1000000000,1]], 1000000000) == 1000000000  # huge interval

assert sol.maximumCoins([[1,3,1],[10,12,10]], 3) == 30  # best window in second segment

assert sol.maximumCoins([[1,4,5],[7,10,2]], 5) == 20  # partial overlap handling

Test Summary

Test	Why
Example 1	Official example with gaps
Example 2	Single segment
[1,5,2], k=5	Window equals segment length
[1,5,2], k=3	Window fully inside one segment
Two separated segments	Must choose better segment
Gap-spanning window	Tests zero-value positions
Single-point segment	Minimum interval size
Huge coordinate range	Validates coordinate compression avoidance
Rich distant segment	Ensures correct maximization
Partial overlap case	Tests boundary calculations

Edge Cases

Window Completely Inside One Segment

A common bug is assuming the optimal window must cross segment boundaries. Consider a segment [1,100] with constant coin value. The best window may lie entirely within that segment.

The implementation handles this naturally because partially covered segments are explicitly accounted for through overlap calculations.

Large Gaps Between Segments

The number line may contain enormous stretches of zero-value bags. A naive solution might try to represent these positions explicitly.

The algorithm never stores individual positions. It works entirely with interval boundaries, so a gap of length 1 and a gap of length 10^9 are handled with the same amount of work.

Optimal Window Ends at a Segment Boundary

If only segment starts are considered, some optimal solutions are missed. For example, the best interval may be characterized by its right endpoint aligning with a segment end.

This is why the mirrored pass is necessary. By reversing coordinates and running the same logic again, every window whose right endpoint is important becomes a window whose left endpoint is important in the transformed space.

Very Large Answers

The maximum possible contribution can be approximately:

10^9 × 1000 = 10^12

which exceeds 32-bit integer limits.

The Python implementation uses arbitrary precision integers automatically. The Go implementation uses int64 for every accumulated sum, ensuring correctness without overflow.