Array-Questions-450DSA.md

Questions:

1. Write a program to reverse an array or string. Given an array (or string), the task is to reverse the array/string. Examples :

Input  : arr\[\] = {1, 2, 3}
Output : arr\[\] = {3, 2, 1}

Input :  arr\[\] = {4, 5, 1, 2}
Output : arr\[\] = {2, 1, 5, 4}

Solution: ReverseArray.cpp Approach:

• Initialize start and end indexes as start = 0, end = n-1
• In a loop, swap arr[start] with arr[end] and change start and end as follows :
  start = start +1, end = end – 1

---

2. Write a C function to return minimum and maximum in an array. Your program should make the minimum number of comparisons.

Solution: Minimum-Maximum-Array1.cpp
Minimum-Maximum-Array2.cpp
Minimum-Maximum-Array3.cpp

We Return Multiple Values from a C function using Structures & Pointers. Start by creating a Structure

struct pair
{
	int min;
	int max;
}

Approach 1: Simple Linear Search

• Initialize values of min and max as minimum and maximum of the first two elements respectively. Starting from 3rd, compare each element with max and min, and change max and min accordingly --> Time Complexity: 0(n)

Approach 2:

• Divide the array into two parts and compare the maximums and minimums of the two parts to get the maximum and the minimum of the whole array.

Approach 3: Compare in Pairs

• If n is odd then initialize min and max as first element.
• If n is even then initialize min and max as minimum and aximum of the first two elements respectively.
• For rest of the elements, pick them in pairs and compare their maximum and minimum with max and min respectively.

---

3. Given an array arr[] and a number K where K is smaller than size of array, the task is to find the Kth smallest element in the given array. It is given that all array elements are distinct.

• Input: N = 6 arr[] = 7 10 4 3 20 15 K = 3 Output : 7 Explanation : 3rd smallest element in the given array is 7.

Solution: k-smallest-element.cpp
Approach: A very simple approach would be sorting the array first and returning the [k-1]th element from the sorted array

---

4. Given an array of size N containing only 0s, 1s, and 2s; sort the array in ascending order. Example 1:

   Input: N = 5 arr[]= {0 2 1 2 0} Output: 0 0 1 2 2

Explanation: 0s 1s and 2s are segregated into ascending order. Solution:

Approach: --> An Efficient solution to this problem is to use a binary search. 
1. For the first occurrence of a number 

a) If (high >= low)
b) Calculate  mid = low + (high - low)/2;
c) If ((mid == 0 || x > arr\[mid-1\]) && arr\[mid\] == x)
         return mid;
d) Else if (x > arr\[mid\])
        return first(arr, (mid + 1), high, x, n);
e) Else
        return first(arr, low, (mid -1), x, n);
f) Otherwise return -1;

2. For the last occurrence of a number 

  a) if (high >= low)
  b) calculate mid = low + (high - low)/2;
  c)if( ( mid == n-1 || x < arr\[mid+1\]) && arr\[mid\] == x )
         return mid;
  d) else if(x < arr\[mid\])
        return last(arr, low, (mid -1), x, n);
  e) else
       return last(arr, (mid + 1), high, x, n);      
  f) otherwise return -1;

---