Category Archives: Array

Subarray with Given Sum

By | | , , ,
Leave a comment

Find subarray with given sum.

Given an array of unsorted integers (Positive integers), We have to write a code to find a subarray whose sum is equal to a given sum.

We have to return subarray indexes (start and end index).

For Example –

  Example 1 :

Input : arr = {10, 2, 4, 7, 5}, sum = 13

Output: {1, 3}

The numbers present from the 1st to 3rd indexes are 2, 4, 7. When we add (2 + 4 + 7) it is 13.

Example 2 :

Input : arr = {1, 4, 20, 3, 10, 5}, sum = 33

  Output: {2, 4}

Example 3 :

  Input : arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, sum = 15

   Output: {0, 4}

→

Insert Delete GetRandom o(1) Solution

By | | , ,
Leave a comment

In this problem, We have to design a data structure that supports Insert, Delete, and GetRandom in average O(1) time.

OR

Design a data structure that supports insert, delete, and getRandom in constant time O(1).

insert(value): Inserts an item value to the set if it’s not present.

remove(value): Removes an item value from the set if present.

getRandom(): Returns a random element from current set of elements. Each element must have the same probability of being returned.

→

Find All Duplicates in an Array

By | | , ,
Leave a comment

How to find all duplicates in an array without using extra space?

Given an array of integers, the integers are in the range of 1 ≤ a[i] ≤ n (n = size of array). In this Array, some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

We have to solve this problem without using extra space and in O(n) time complexity.

For Example:

Input: [4, 3, 2, 7, 8, 2, 3, 1]

Output: [2, 3]

→