What is the brute force approach and complexity for Subarray with Given Sum (non-negative numbers)?

For every start, extend the end and compare the running sum with target with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Subarray with Given Sum (non-negative numbers)?

Grow right; while sum > target, drop from the left; stop when sum == target with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Subarray with Given Sum (non-negative numbers)?

Look for key signals in the prompt: "continuous subarray" indicates The answer is a range [left … right] → think window.; "sum equals target" indicates A sum can be updated in O(1) as elements enter and leave.; "non-negative integers" indicates Growing never lowers the sum, shrinking never raises it. This is the condition that makes the window safe.; "first subarray / 1-based indices" indicates Return as soon as you find a match, and add 1 to both indices..

Subarray with Given Sum (non-negative numbers)

Easy·GeeksforGeeks Pro OnlyBasic Reinforcement

GeeksforGeeks

Problem Statement

You are given an array arr of non-negative integers (zeros are allowed) and a number target.

Find a contiguous subarray whose sum is exactly target. Return its start and end positions as 1-based indices, [start, end]. If several subarrays work, return the first one (the one that starts furthest left). If none works, return [-1].

In this walkthrough the subarray must have at least one element. So for target = 0, the answer is the position of the first 0 in the array, or [-1] if there is no zero.

Input

An integer array arr of non-negative numbers, and an integer target.

Output

A list [start, end] with 1-based positions, or [-1] if no subarray sums to target.

Example 1

Input: arr = [1, 2, 3, 7, 5], target = 12

Output: [2, 4]

Positions 2 to 4 hold 2 + 3 + 7 = 12. ([7, 5] also adds to 12, but it starts later.)

Example 2

Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], target = 15

Output: [1, 5]

1 + 2 + 3 + 4 + 5 = 15, starting at the very first position.

Example 3

Input: arr = [5, 3, 4], target = 2

Output: [-1]

Every element is bigger than 2, so no subarray can add up to exactly 2.

Example 4

Input: arr = [3, 0, 4, 0], target = 0

Output: [2, 2]

The subarray must not be empty. The first one with sum 0 is the single 0 at position 2.

Constraints

• 1 ≤ arr.length ≤ 10^6
• 0 ≤ arr[i] ≤ 10^3
• 0 ≤ target ≤ 10^9
• Sums can reach 10^9 — keep them in a 64-bit type to be safe.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“continuous subarray”

→ The answer is a range [left … right] → think window.

“sum equals target”

→ A sum can be updated in O(1) as elements enter and leave.

“non-negative integers”

→ Growing never lowers the sum, shrinking never raises it. This is the condition that makes the window safe.

“first subarray / 1-based indices”

→ Return as soon as you find a match, and add 1 to both indices.

Approach Complexity Ladder

Brute Force — check every subarrayO(N²)O(1)

For every start, extend the end and compare the running sum with target

Better — prefix sums + hash mapO(N)O(N)

A subarray sums to target when two running totals differ by target

Optimal — variable sliding windowO(N)O(1)

Grow right; while sum > target, drop from the left; stop when sum == target

Brute Force Intuition

Go through starts from left to right. For each start, extend the end one step at a time, keeping a running sum. The first time the sum equals target, return that range. Because we try starts in order, the first match has the smallest start.

Recognition rule for this sub-pattern:

Window grows and shrinks. Expand right; when the window breaks the rule, move left until it is valid again. Works when "bigger window = harder to be valid".

Remember this · Sliding Window

Trigger

Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".

Think

Can I keep a valid range and move it, instead of checking every subarray from scratch?

Key question

When is my current window valid?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

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 Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Minimum Size Subarray Sum Longest Substring Without Repeating Characters