Data Structure - Array

Q:- Find largest element in an array?
A:- The solution is to initialize max as first element, then traverse the given array from second element till end. For every traversed element, compare it with max, if it is greater than max, then update max.
Time complexity of the above solution is O(n).

Q:- Find Second largest element in an array?
A:-  A simple solution will be first sort the array in descending order and then return the second element from the sorted array. The time complexity of this solution is O(n Log n).

A Better Solution is to traverse the array twice. In the first traversal find the maximum element. In the second traversal find the greatest element less than the element obtained in first traversal. The time complexity of this solution is O(n*n).

A more Efficient Solution can be to find the second largest element in a single traversal. The time complexity of this solution is O(n).

1) Initialize two variables first and second to INT_MIN as,
   first = second = INT_MIN
2) Start traversing the array,
   a) If the current element in array say arr[i] is greater
      than first. Then update first and second as,
      second = first
      first = arr[i]
   b) If the current element is in between first and second,
      then update second to store the value of current variable as
      second = arr[i]
3) Return the value stored in second.

Q:- Find the smallest and second smallest elements in an array?
A:- A Simple Solution is to sort the array in increasing order. The first two elements in sorted array would be two smallest elements. Time complexity of this solution is O(n Log n).

A Better Solution is to scan the array twice. In first traversal find the minimum element. Let this element be x. In second traversal, find the smallest element greater than x. Time complexity of this solution is O(n * n).

The above solution requires two traversals of input array.

An Efficient Solution can find the minimum two elements in one traversal. Below is complete algorithm. Time complexity of this solution is O(n).

1) Initialize both first and second smallest as INT_MAX
   first = second = INT_MAX
2) Loop through all the elements.
   a) If the current element is smaller than first, then update first
       and second.
   b) Else if the current element is smaller than second then update
    second

Q:- Recursive program to linearly search an element in a given array?

class Test
{
     static int arr[] = {12, 34, 54, 2, 3};
     
/* Recursive Method to search x in arr[l..r] */
     static int recSearch(int arr[], int l, int r, int x)
     {
          if (r < l)
             return -1;
          if (arr[l] == x)
             return l;
          return recSearch(arr, l+1, r, x);
     }
     
     public static void main(String[] args)
     {
        int x = 3;
        int index = recSearch(arr, 0, arr.length-1, x);
        if (index != -1)
           System.out.println("Element " + x + " is present at index " +
                                                    index);
        else
            System.out.println("Element " + x + " is not present");
     }
 }

Q:- Find the largest three elements in an array?
A:- Expected time complexity is O(n) and extra space is O(1).

1) Initialize the largest three elements as minus infinite.
    first = second = third = -∞

2) Iterate through all elements of array.
   a) Let current array element be x. int x= arr[0];
   b) If (x > first)
      {
          // This order of assignment is important
          third = second
          second = first
          first = x  
       }
   c)  Else if (x > second)
      {
          third = second
          second = x
      }
   d)  Else if (x > third)
      {
          third = x 
      }

3) Print first, second and third. 

Q:- Program to cyclically rotate an array by one?
Input:  arr[] = {1, 2, 3, 4, 5}
Output: arr[] = {5, 1, 2, 3, 4}
A:-
Following are steps.
1) Store last element in a variable say x.
2) Shift all elements one position ahead.
3) Replace first element of array with x.

Time Complexity: O(n)
Auxiliary Space: O(1)

Q:- Segregate 0s and 1s in an array?
Input array   =  [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]
Output array =  [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]   
A:- Method 1 (Count 0s or 1s)
1) Count the number of 0s. Let count be C.
2) Once we have count, we can put C 0s at the beginning and 1s at the remaining n – C positions in array.

Time Complexity: O(n)

The method 1 traverses the array two times. Method 2 does the same in a single pass.

Method 2 (Use two indexes to traverse)
Maintain two indexes. Initialize first index left as 0 and second index right as n-1.

Do following while left < right
a) Keep incrementing index left while there are 0s at it
b) Keep decrementing index right while there are 1s at it
c) If left < right then exchange arr[left] and arr[right]

Q:- Find duplicates in O(n) time and O(1) extra space?
A:-