Interview Preparation

An element is leader if it is greater than all the elements to its right. The last array element is a leader by default. Example: Input:  {16, 17, 4, 3, 5, 2} Output: 2, 5, 17 Concept: Scan form right. Keep track of maximum element. If the maximum changes print the element and update the maximum. Time complexity O(n). Code: import java.util.*; public class Solution {          public static void main(String[] args) {         int[] a = {1,10,4,5,3,2};         int n = a.length;         int max = a[n-1];                  System.out.print(max+" ");         for(int i=n-2; i>=0; i--){             if(a[i] > max){                 System.out.print(a[i]+" ");                 max = a[i];     ...

Given an array where only two elements where swapped , sort the array with O(n) time complexity and one swap Input: arr[] = {10, 20, 60, 40, 50, 30} // 30 and 60 are swapped Output: arr[] = {10, 20, 30, 40, 50, 60} Input: arr[] = {10, 20, 40, 30, 50, 60} // 30 and 40 are swapped Output: arr[] = {10, 20, 30, 40, 50, 60} Input: arr[] = {1, 5, 3} // 3 and 5 are swapped Output: arr[] = {1, 3, 5} Concept behind:   If you swap two elements in a sorted(ascending) array, the first out of order element will be greater than its next element and the next out of order element will be less than its previous element. Consider:  {10, 20, 40, 30, 50, 60}  Here the first out of order element is 40( 40 > 30) -> a[i] > a[i+1] The next out of order element is  30 (30 < 40) -> a[i] < a[i-1] Hence we will first find the first out of order element and from the next element we check for the other out of order element using the above condition...

Given an array find the the maximum difference between any two elements provided larger element appears after the smaller. Input : arr = {2, 3, 10, 6, 4, 8, 1} Output : 8 Explanation : The maximum difference is between 10 and 2. Input : arr = {7, 9, 5, 6, 3, 2} Output : 2 Explanation : The maximum difference is between 9 and 7. Concept behind: We can easily find the solution in O(n) time complexity and O(1) space complexity. We will keep track of minimum element found so far. We compare it with the successive elements, if the difference is greater then we will update it. And we check if the element is current minimum and update the minmum.   In precise, while iterating, the element might be a minimum or maximum element. If it's maximum then the difference will obviously greater than the diff so far. Hence we keep track of minimum alone. Code: import java.util.*; public class Solution {          public static void main(Strin...