How to Find Subarray with Given Sum?

Are you searching for a method to find a subarray that adds up to a specific sum? Look no further! Let’s explore different methods to find subarrays with a given sum.

[{"selector":"#anim-0e873165-e3fc-46e8-8b19-ca7168ccaa34","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-31b812dc-7c4b-4961-8b6b-071237e826c8","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-077d633d-f54e-4039-947b-f263f971c861 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

Given an array of integers, the goal is to locate a non-empty subarray that adds up to the specified sum. Sound complicated?

[{"selector":"#anim-34b2fbd6-3ae6-4ba4-b512-7e39f27e9036 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-4d6db40a-e595-4b5a-9ee0-ad0449333812","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-170aa82d-0c1f-44c8-9dff-58d8638fd949","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-f5924d1e-b742-4b0a-bec0-954fd428a025","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-a2af5277-acfd-4632-a35f-976f365a298b","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

Example- Input: [11, 9, 8, 7, 13, 5, 17] Sum: 25 Output: YES Explanation: The subarray [7, 13, 5] adds up to 25.

[{"selector":"#anim-f209e526-63dc-4ad7-803f-8dade928b52f","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-a2f8c6c8-cd77-4a98-9532-fb9c2c0a7e10","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-a1b54f34-e173-404c-bbd0-2b81c705ab18 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

Approach 1- Naive Approach

[{"selector":"#anim-87186248-6afa-4af7-a630-7a8ec9c83124 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-2091cba8-6964-43ba-98f9-78a47bee1e26","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-ce30cb53-f441-45b6-aeaa-e8be08bbb892","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-cea435e3-316c-4570-9cf9-887bde4a5224","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-b60dc9f0-a630-449a-9adc-83a69e80257f","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

Time complexity: O(N^2), where N is the size of the array. Space complexity: O(1)

[{"selector":"#anim-fa0a2111-66f7-438e-a505-13593cc0f748 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-043fc9a1-b125-4db0-b029-54dd40b26d9f","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-db3e5859-4293-4efb-a204-3a6ab7f72300","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

Speed up your search for the perfect subarray with this approach. It involves taking an empty window and adjusting it until the given constraint is satisfied. Ready to see how it works? Check out the algorithm!

[{"selector":"#anim-41828564-2035-4226-b485-a8d4f41285c0","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-5592058d-8abc-4ad3-80a3-65c25c494bbb","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-2d333dbf-1737-44c3-9d96-ed89524782e0 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-d6846689-7dab-4bba-af38-ab32fbc4b8e4","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-d9fe7a7c-e317-41e4-a986-7dcdd58fd326","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

Click on the link below to start your journey.

[{"selector":"#anim-9fc462a8-703f-4024-9a27-b94f76fac234","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-056ba4dc-cc6b-4095-95b1-ee3f1d6a79f8","keyframes":{"transform":["translate3d(-105.86593%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-f334c298-659e-4274-a03b-5a15bb6669a2","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-c2290685-2307-4132-adef-99928c682c8f","keyframes":{"transform":["translate3d(0px, -260.77716%, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] Click here

Don't miss out on the chance to upskill yourself with IntervewBit's engaging web stories.

[{"selector":"#anim-7fe7cef5-f27a-46cc-b605-9573d38a9d5f","keyframes":{"opacity":[0,1]},"delay":0,"duration":1000,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-a42ccde9-0efb-4a03-a02e-792c53172940","keyframes":{"transform":["translate3d(0px, -211.49618%, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":1000,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-3167db06-fdbb-4dcc-a33d-5b60ce968d28","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-085ec2f3-fb56-49bf-b5b1-8ccd824c75ac","keyframes":{"transform":["translate3d(0px, -621.00265%, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] Step Up Your Game with InterviewBit Web Stories SWIPE UP

How to Find Subarray with Given Sum?

A Quick Guide

Are you searching for a method to find a subarray that adds up to a specific sum? Look no further! Let’s explore different methods to find subarrays with a given sum.

Given an array of integers, the goal is to locate a non-empty subarray that adds up to the specified sum. Sound complicated?

Problem Statement

Example- Input: [11, 9, 8, 7, 13, 5, 17] Sum: 25 Output: YES Explanation: The subarray [7, 13, 5] adds up to 25.

Approach 1- Naive Approach

The naive approach involves checking every single subarray for the given sum. Are you ready to see it in action?

Time complexity: O(N^2), where N is the size of the array. Space complexity: O(1)

Speed up your search for the perfect subarray with this approach. It involves taking an empty window and adjusting it until the given constraint is satisfied. Ready to see how it works? Check out the algorithm!

Approach 2- Sliding window

Click on the link below to start your journey.

Are you ready to level up your coding skills?

Don't miss out on the chance to upskill yourself with IntervewBit's engaging web stories.

“