This week’s session is headlined by Arun. We will cover a few questions based on Array data structure. This is work in progress, question may change before they are announced in the meetup.

2SUM Problem: Given an array of integers a[] and a target sum T, find two indices (i and j) such that a[i] + a[j] adds up to T. Return both the indices int[] TwoSum(int a[], int T) Easy: O(n^{2})
Easy-Moderate: O(n log n)
Moderate: O(n), Can use extra space.

Find Duplicate: Given an array of integers a[] of size (n+1), and every number is between 1 and n. This means that there would be at least one duplicate integer. Find it. Note: There may be more than one duplicate, return any of them. A number may appear more than twice.
Easy: O(n^{2}) time, O(1) space
Moderate: O(n) time, O(n) space.
Moderate-Hard: O(n) time, O(1) space, if you can make the array mutable.

Find in Rotated Sorted Array: Given an array of integers a[] that is sorted, and then cut into two parts (LEFT and RIGHT). The array is now spliced back RIGHT and LEFT. So a will look like 4 5 6 70 1 2.

Find the smallest element in the array?

Find the largest element in the array?

Find the k^{th} largest element in the array?

Find the index of a given element in the array?
Easy: O(n)
Easy-Moderate: O( log n)

Filling Water: Assume you are given a bar graph chart, where the width of each bar 1 unit, and the height is provided in an array of ints. If you “flood” the graph now, calculate the total water that will be retained in the shape.
Example: If the input is : Given [0,1,0,2,1,0,1,3,2,1,2,1]. It represents, a bar of 0 height at 0th location, 1 in 1st location, 0 in 2nd location and so on. If you flood the graph with water, you will have 1 unit between 1st and 3rd bars, 4 units between 3rd and 7th bars, 1 unit between 8 and 10th bars. So net output is 6 Easy: O(n^{2}) time, O(1) space
Moderate-Hard: O(n) time, O(n) space

Combined Median: Given two sorted arrays, a[] and b[] of size n,