Arrays

An array is a collection of items of the same data type stored at contiguous memory locations. The size of the array is fixed and the memory for an array needs to be allocated before use, the size of an array cannot be increased or decreased dynamically.

dataType arrayName[arraySize];

dataType arrayName[] = {1, 2, 3, 4, ...};

Elements in an array can be accessed using indexes. Suppose an array named arr stores N elements. Indexes in an array are in the range of 0 to N-1.

Related Topics:

• Insertion and Deletion in arrays. O(n)
• Searching an Element.
  • Linear Search O(n)
  • Binary Search O(logn)
• Reversing an Array. O(n)
• Rotating an Array. O(n)
• Sliding Window Technique.
• Sorting an array.
  • Bubble O(n^2)
  • Selection O(n^2)
  • Insertion O(n^2)
  • Quick O(nlogn), O(n^2)
  • Merge O(nlogn)
• Dynamic Arrays - Vectors (STL)
  • pop()
  • push()

Questions

S. No	Problem	Solutions
1	Reverse the array	O(n)
2	Find the maximum and minimum element in an array	<->
3	Find the "Kth" max and min element of an array	<->
4	Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo	<->
5	Move all the negative elements to one side of the array	<->
6	Find the Union and Intersection of the two sorted arrays.	<->
7	Write a program to cyclically rotate an array by one.	<->
8	find Largest sum contiguous Subarray	<->
9	Minimise the maximum difference between heights	<->
10	Minimum no. of Jumps to reach end of an array	<->
11	find duplicate in an array of N+1 Integers	<->
12	Merge 2 sorted arrays without using Extra space.	<->
13	Kadane's Algo	<->
14	Merge Intervals	<->
15	Next Permutation	<->
16	Count Inversion	<->
17	Best time to buy and Sell stock	<->
18	find all pairs on integer array whose sum is equal to given number	<->
19	find common elements In 3 sorted arrays	<->
20	Rearrange the array in alternating positive and negative items with O(1) extra space	<->
21	Find if there is any subarray with sum equal to 0	<->
22	Find factorial of a large number	<->
23	find maximum product subarray	<->
24	Find longest consecutive subsequence	<->
25	Given an array of size n and a number k, find all elements that appear more than " n/k " times.	<->
26	Maximum profit by buying and selling a share atmost twice	<->
27	Find whether an array is a subset of another array	<->
28	Find the triplet that sum to a given value	<->
29	Trapping Rain water problem	<->
30	Chocolate Distribution problem	<->
31	Smallest Subarray with sum greater than a given value	<->
32	Three way partitioning of an array around a given value	<->
33	Minimum swaps required bring elements less equal K together	<->
34	Minimum no. of operations required to make an array palindrome	<->
35	Median of 2 sorted arrays of equal size	<->
36	Median of 2 sorted arrays of different size	<->