Array - DSA Questions

A10.swift

// Print all Divisors of a given Number | A10.swift

var arr = [Int]()
    
    // x = sqr(n)
    // TimeComlexity = O(x + xlog(x) + x)
    
    for i in 1...n where i * i <= n {
        if n % i == 0 {
            arr.append(i)
            if n/i != i {
                arr.append(n/i)
            }
        }
    }
    
    // Tc -> nlog(n)
    arr.sort()
    
    for i in arr {
        print(i, terminator: " ")
    }

A11.java

// Union of Two Sorted Arrays.

// Problem Link: https://www.geeksforgeeks.org/problems/union-of-two-sorted-arrays-1587115621/1
// Brute Force Approch

// TC -> O(nlogk) + O(mlogk) + O(n+m)
// where k is size of set.

// SC -> O(n+m) + O(n + m)
// 1. O(n+m) -> For solve the problem
// 2. O(n+m) -> For return the answer.

import java.util.*; 

public static ArrayList<Integer> findUnion(int arr1[], int arr2[], int n, int m)
{
    SortedSet<Integer> ss = new TreeSet<Integer>();

    for(int i = 0; i < n; i++) {
        ss.add(arr1[i]);
    }

    for(int i = 0; i < m; i++) {
        ss.add(arr2[i]);
    }

    return new ArrayList<Integer>(ss);
}

// Optimal Approch
// Please pay attension, both array's is sorted and can contains duplicates.
// The araylist you return must be in sorted order too.

// Intituion ( two pointer approch )
// 1. We will pick smallest element by comparing both array elements.
// 2. Also check if it is already exists in resultant array then we will not add, becuase resultant array should
// not contains duplicates elements.
// 3. When one of array is exhaused, iterate other array elements to put in resultant array.

public static ArrayList<Integer> findUnion(int arr1[], int arr2[], int n, int m)
{
    ArrayList<Integer> unionList = new ArrayList<Integer>();

    int i = 0, j = 0;

    while(i < n && j < m) {

        int element;

        if(arr1[i] < arr2[j]) {
            element = arr1[i];
            i++;
        }
        else if(arr2[j] < arr1[i]) {
            element = arr2[j];
            j++;
        }
        else {
            element = arr1[i];
            i++; j++;
        }

        int size = unionList.size();
        if (size == 0 || (size > 0 && element != unionList.get(size - 1))) {
            unionList.add(element);
        }
    }

    for(int k = i; k < n; k++) {
        if (arr1[k] != unionList.get(unionList.size() - 1)) {
            unionList.add(arr1[k]);
        }
    }

    for(int k = j; k < m; k++) {
        if (arr2[k] != unionList.get(unionList.size() - 1)) {
            unionList.add(arr2[k]);
        }
    }

    return unionList;
}

A12.swift

// 26. Remove Duplicates from Sorted Array.

// Problem Link: https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

// Brute Force Approch
// Use ordered SET.

// Optimal Approch - 2 ( Using two pointer approch )
// TC -> O(n)
// SC -> O(1)

// Intituion
// 1. As we know unique element should be next to unique element.
// 2. So, we will consider first element as unique, put a pointer on it as 'j'.
// 3. Then, iterate array from index 1 until we found element different from element at index 'j'.
// 4. When new unique element found, increase the 'j' pointer by 1 and place new element at new index of 'j'.
// 5. Repeat the process.

func removeDuplicates(_ arr: inout [Int]) -> Int {
         var i = 1, j = 0, n = arr.count

        while(i < n) {
            if arr[j] != arr[i] {
                j += 1
                arr[j] = arr[i]
            }
            i += 1
        }

        return j + 1
}

A13.swift

// Right rotate an array by D places | A13.swift

// Problem Link: https://leetcode.com/problems/rotate-array/

// Brute Force Approach

// TC -> O(k * n)
// SC -> O(1)

// Right rotating one by one.

func rotate(_ arr: inout [Int], k: Int) {
    let n = arr.count;
    var k = k % n;

    for _ in 0..<k {
         var temp = arr[n - 1];

        for j in stride(from: n-1, to: 0, by: -1) {
            arr[j] = arr[j - 1];
        }

        arr[0] = temp;
    }
}

// Best Approach 
// TC -> O(n)
// SC -> O(n)

// Explanation
// Suppose you have an array A.
// And an array B which is right rotated by k.
// then A[i] == B[(n - k + i) % n] for sure.

func rightRotate1(arr: [Int], by k: Int) -> [Int] {
    let n = arr.count
    let k = k % n

    var newArr = Array<Int>(repeating: 0, count: n)
    
    for i in arr.indices {
        newArr[i] = arr[(n - k + i) % n]
    }
    
    return newArr
}

// Optimal Approch
// TC -> O(2n)
// SC -> O(1)

func rightRotate(arr: inout [Int], by k: Int) -> [Int] {
    let n = arr.count
    
    var k = k % n
    k = n - k
    
    if k != 0 {
        reverse(arr: &arr, start: 0, end: k-1)
        reverse(arr: &arr, start: k, end: n-1)
        reverse(arr: &arr, start: 0, end: n-1)
    }
    return arr
}

func reverse(arr: inout [Int], start: Int, end: Int) {
    var start = start
    var end = end
    while start < end {
        arr.swapAt(start, end)
        start += 1
        end -= 1
    }
}

A14.swift

// Left rotate an array by D places | A14.swift

// Not able to find left rotate array problem
// so here is right rotate array problem Link: https://leetcode.com/problems/rotate-array/

// Brute Force Approch 
// TC -> O(n)
// SC -> O(n)

// Explanation
// Suppose you have an array A.
// And an array B which is left rotated by k.
// then A[i] == B[ (k+i) % n] for sure.

func leftRotate1(arr: [Int], by k: Int) -> [Int] {
    let n = arr.count
    let k = k % n

    var newArr = Array<Int>(repeating: 0, count: n)
    
    for i in arr.indices {
        newArr[i] = arr[(k + i) % n]
    }
    
    return newArr
}

// Optimal Approch
// TC => O(2n)
// SC => O(1)

func leftRotate(arr: inout [Int], by k: Int) -> [Int] {
    let n = arr.count
    
    let k = k % n
    
    if k != 0 {
        reverse(arr: &arr, start: 0, end: k-1)
        reverse(arr: &arr, start: k, end: n-1)
        reverse(arr: &arr, start: 0, end: n-1)
    }
    return arr
}

func reverse(arr: inout [Int], start: Int, end: Int) {
    var start = start
    var end = end
    while start < end {
        arr.swapAt(start, end)
        start += 1
        end -= 1
    }
}

A15.swift

// Merge 2 Sorted Array | A15.java

// Problem Link: https://www.naukri.com/code360/problems/sorted-array_6613259

// Brute Force Approch

// Thought Process
// First, I'm collecting both the array elements into one new array which costs me O(n+m) time complexity and O(n+m)
// space complexity.
// Next, I'm sorting the array in-place which cost me arround O(klogk) where k = n+m
// Next, I'm removing any duplicates from sorted array, cost O(n+m) time complexity.

// Total TC-> O(k + klogk + k)
// SC -> O(k)
// where k = n+m

public static List< Integer > sortedArray(int []a, int []b) {
  List<Integer> list = new ArrayList<Integer>();

  int n = a.length;
  int m = b.length;

  for (int i = 0; i < n; i++) {
      list.add(a[i]);
  }

  for (int i = 0; i < m; i++) {
      list.add(b[i]);
  }

  Collections.sort(list);

  int i = 0;

  while (i <= list.size() - 2) {
      if (list.get(i) == list.get(i + 1)) {
          list.remove(i + 1);
      }
      else {
          i += 1;
      }
  }

  return list;
}  


// Using TreeSet in Java.

// Time Complexity => O(n + m) if we exclude the conversion into ArrayList.
// else TC will be => O(n + m + (n+m)log(n+m))
// SC=> O(n + m) if we exclude the conversion into ArrayList.

public static List< Integer > sortedArray(int []a, int []b) {

    SortedSet<Integer> unioIntegers = new TreeSet<>();

    int n = a.length, m = b.length;

    for (int i = 0; i < n; i++) {
        unioIntegers.add(a[i]);
    }

    for (int i = 0; i < m; i++) {
        unioIntegers.add(b[i]);
    }

    return new ArrayList<>(unioIntegers);
}
    
// Optimal Approch !!

// TC -> O(n+m)
// SC -> O(n+m)

// Thought Process ( Two Pointer Approch )
// Put pointers on the first element of both arrays.
// Compare the elements if one of them is smaller, then consider that elemenet.
// Check if this element is not the last element of our new array, then add it to the new array.
// Pick the remaining elements of array by using loops.

public static List< Integer > sortedArray(int []a, int []b) {

  List<Integer> list = new ArrayList<Integer>();

  int n = a.length, m = b.length, 
      i = 0, j = 0;

  while (i < n && j < m) {

      int ele;

      if (a[i] > b[j]) {
          ele = b[j];
          j++;
      }
      else {
          ele = a[i];
          i++;
      }

      if (list.size() == 0 || list.get(list.size() - 1) != ele) {
          list.add(ele);
      }
  }

  int last = list.get(list.size() - 1);

  if (i != n) {
      for (int k = i; k < n; k++) {
          if (last != a[k]) {
              list.add(a[k]);
              last = a[k];
          }
      }
  }
  else if (j != m) {
      for(int k = j; k < m; k++) {
          if (last != b[k]) {
              list.add(b[k]);
              last = b[k];
          }
      }
  }

  return list;
}

A16.swift

// Move all Zeros to the end of the array | A16.swift

int[] arr = [1, 2, 0, 0, 2, 3];

//Brute Force Approch
1. Save all non-zero elements into temp array. 
2. Fill non-zero elements from temp into the first of the given array.
3. Fill zero's to the remaining.

TC -> O(n + x + n - x) => O(2n)
SC -> O(n) ( Worst case )

-----------------------

//Optimal Approch
TC -> O(n)
SC -> O(1)

// Find first zero in the array.

  int j = -1;

  for(int i = 0; i < n; i++) {
      if(arr[i] == 0) {
          j = i;
          break;
      }
  }   

  // If no zero found then return !
  if(j == -1) return arr;

 // Iterate and swap 
 
  for(int i = j + 1; i < n; i++) {
    if(arr[i] != 0) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        j++;
    }
  }
  
  return arr;

A17.swift

// Find the missing number in the array >> A17.swift

// Problem Link: https://leetcode.com/problems/missing-number/

//Brute force approch
// TC -> O(n*n)
// SC -> O(1)

// ThoughtProces
// 1. Check every number from range [0...n] in array.
// 2. if it is not exist return that number.

func missingNumber(_ nums: [Int]) -> Int {
        
    let n = nums.count
        
    for i in 0...n {
        var found = false
        for j in nums {
            if i == j {
                found = true
                break
            }
        }
        if found == false {
            return i
        }
    }

    return -1
}


// Best Approch
// Hasing

// TC -> O(2n)
// SC -> O(N)

func missingNumber(_ nums: [Int]) -> Int {
    let n = nums.count
    
    var arr = Array<Int>(repeating: 0, count: n + 1)

    for i in nums {
        arr[i] = 1
    }

    for i in arr.indices {
        if arr[i] == 0 {
            return i
        }
    }

    return -1
}

// Optimal approch !
// TC -> O(N)
// SC -> O(1)

// ThoughtProcess
// Use the sum of natural number formaula to calculate the sum.
// And then subtract it from available array elements sum.
func missingNumber(_ nums: [Int]) -> Int {

    let n = nums.count
    var sum = 0

    for i in nums {
        sum += i
    }

    return ((n * (n + 1)) / 2) - sum
}

A18.swift

// Find the number that appears once, and the other numbers twice (LC: 136. Single Number )

// Problem Link: https://leetcode.com/problems/single-number/description/

// Brute force approch
// TC -> O(n*n) ( nearby )
// SC -> O(1)

// Thought Process:
// 1. Take one element from array and check for it's duplicates using another loop.
// 2. If it's exists do nothing, it not return that element.

func singleNumber(_ nums: [Int]) -> Int {
  let n = nums.count

  for i in nums.indices {
      var found = false

      for j in nums.indices {
          if nums[i] == nums[j] && i != j {
              found = true
              break
          }
      }

      if found == false {
          return nums[i]
      }
  }

  return -1
}
    

// Best Approch ( Using dictionaries )
// TC -> O(n) + O(1) + O(n/2 + 1)
// O(1) = For element lookups in dictionary
// SC -> O(n/2 + 1)

// Thought Process
// 1. We will iterate over the array and store elements frequencies in dictionary.
// 2. Then we will iterate over the dictionary and check any elements has value 1.
// 3. Return the key of that element if it's exist otherwise return -1.

func singleNumber(_ nums: [Int]) -> Int {

    var dict: [Int: Int] = [:]

    for ele in nums {
        if dict[ele] != nil {
            dict[ele]! += 1
        }
        else {
            dict[ele] = 1
        }
    }

    for key in dict.keys {
        if dict[key] == 1 {
            return key
        }
    }

    return -1
}

// Optimal Approch
// TC -> O(n)
// SC -> O(1)

func singleNumber(_ nums: [Int]) -> Int {

  var result = 0
  for ele in nums {
      result ^= ele
  }
  return result
}

A19.java

// Longest Subarray with given Sum K ( Positives and Positives + Negatives )

// Problem Link: ( GFG ) https://www.geeksforgeeks.org/problems/longest-sub-array-with-sum-k0809/1
// Striver: https://takeuforward.org/data-structure/longest-subarray-with-given-sum-k/

//Brute Force Approch
// TC -> O(n*n)
// SC -> O(1)

// ThoughtProcess
// 1. We will generate all the subarrays.
// 2. And then check if sum if equal to K.

public static int lenOfLongSubarr (int arr[], int n, int k) {
  int maxCount = 0;
  
  for(int i = 0; i < n; i++) {
      int tCount = 0;
      int tSum = 0;

      for(int j = i; j < n; j++) {
          tSum += arr[j];
          tCount++;
          if(tSum == k) {
              maxCount = tCount > maxCount ? tCount: maxCount;
          }
      }
  }
  return maxCount;
}

// Better Approch ( Reverse Engineering )
// TC -> O(n)
// SC -> O(n)

// Thought Process
// 1. Suppose you're at index i in the array and upto index i your sum is x.
// 2. if there is a subarray exits upto that index i and below the index i whose sum is equal to k,
// then might also be subarray exists whose sum is x-k.
// 4. So from index 0, you will be storing sum and index in hashmap.
// 5. if you find x-k sum any moment, then you find subarray sum equal to k.

// Special Case -> [2, 0, 0, 0, 5] K = 5, then longest subarray length = 4, not 1.

// Note:  This will work when elements are positive, negatives or both.
public static int lenOfLongSubarr (int arr[], int n, int k) {
  
    HashMap<Integer, Integer> hashMap = new HashMap<>();

    int sum = 0;
    int maxLength = 0;

    for(int i = 0; i < n; i++) {
        sum += arr[i];

        // Special case handling.
        if(hashMap.containsKey(sum) == false) {
            hashMap.put(sum, i);
        }

        if(sum == k && i + 1 > maxLength) {
            maxLength = i + 1;
        }
        else if (hashMap.containsKey(sum - k)) {
            int index = hashMap.get(sum - k);
            int tCount = i - index;

            if(tCount > maxLength) 
                maxLength = tCount;
        }
    }

    return maxLength;
}

// Optimal Approch for ONLY POSITIVES
// TC -> O(2n)
// SC -> O(1)

// Thought Process 
// 1. Whenever sum is greater than k shrink it from left.
// 2. Now check it's sum is equal to k or not.

public static int lenOfLongSubarr (int arr[], int n, int k) {
  int left = 0, right = 0;
  int maxLength = 0, sum = 0;

  while(right < n) {
    sum += arr[right];

    while(sum > k) {
        sum = sum - arr[left];
        left++;
    }

    if (sum == k) {
        int tLength = right - left + 1;
        if(tLength > maxLength) {
            maxLength = tLength;
        }
    }
  }
 return maxLength;
}

A20.swift

// Two Sum : Check if a pair with given sum exists in Array ( 1. Two Sum )

// Problem Link: https://leetcode.com/problems/two-sum/description/
// Article Link: https://takeuforward.org/data-structure/two-sum-check-if-a-pair-with-given-sum-exists-in-array/

// Brute Force Approch
// O(n * n)
// TC -> O(1)

// ThoughtProcess
// 1. Check one element with every other element.

func twoSum(_ arr: [Int], _ target: Int) -> [Int] {
        
    let n = arr.count

    for i in arr.indices {
        for j in i+1..<n {
            if arr[i] + arr[j] == target {
                return [i, j]
            }
        }
    }
    return [-1, -1]
}

// Better Approch
// TC -> O(N) + O(1)
// SC -> O(N)

// Thought Proces
// 1. Consider an array element x and subtract it from target t.
// 2. y = t - x
// 3. Now you have to find weather y is exits in array or not
// 4. If yes return x index + y index.
// 4. You can use dictionary for efficently element lookups.

func twoSum(_ arr: [Int], _ target: Int) -> [Int] {
    
  let n = arr.count

  var dict: [Int: Int] = [:]

  for i in arr.indices {
      if let index2 = dict[target - arr[i]] {
          return [index2, i]
      }
      dict[arr[i]] = i
  }
        
  return [-1, -1]
}

// Best Approch - 2 ( two pointer approch )
// 1. Sort the array.
// 2. Put a pointer on 0 as left and n-1 as right.
// 3. Sum = left + right and check if equal to target.
// 4. if sum > target then right-- else left++

A21.swift

// Sort an array of 0s, 1s and 2s (LC: 75. Sort Colors)

// Problem Link: https://leetcode.com/problems/sort-colors/
// Article Link: https://takeuforward.org/data-structure/sort-an-array-of-0s-1s-and-2s/

// Brute Force approach -> Sorting Alogo's.

// Better approach
// TC -> O(n) + O(n)
// SC -> O(1)

// Thought Process
// 1. As you know, array only contains 0, 1 and 2.
// 2. Consider three variable for the elements respectively.
// 3. Store the count on these variables.
// 4. Then, refill the array according to count.

func sortColors(_ nums: inout [Int]) {
  var zero = 0, one = 0, two = 0

  for ele in nums {
      if ele == 0 {
          zero += 1
      }
      else if ele == 1 {
          one += 1
      }
      else {
          two += 1
      }
  }

  var i = 0
  for _ in 0..<zero {
      nums[i] = 0
      i += 1
  }

  for _ in 0..<one {
      nums[i] = 1
      i += 1
  }

  for _ in 0..<two {
      nums[i] = 2
      i += 1
  }
}
  
  
// Optimal Approch ( Dutch National Flag Algorithm )
// TC => O(n)
// SC => O(1)

// Intituion or Thought Process
// Consider the rules
// 1.  0 -> low - 1 will contains only 0's.
// 2. low -> mid - 1 will contains only 1's.
// 3. mid -> high can contains 0, 1 and 2's.
// 4. high + 1 -> n - 1 will contains only 2's.

func sortColors(_ arr: inout [Int]) {
   var low = 0, mid = 0, high = arr.count - 1

   while(mid <= high) {
    if arr[mid] == 0 {
      (arr[mid], arr[low]) = (arr[low], arr[mid])
        mid += 1
        low += 1            
    }
    else if arr[mid] == 1 {
        mid += 1
    }
    else {
        (arr[mid], arr[high]) = (arr[high], arr[mid])
        high -= 1
    }
   }
}

A22.swift

// Find the Majority Element that occurs more than N/2 times.

// Problem Link: https://leetcode.com/problems/majority-element/description/
// Article Link: https://takeuforward.org/data-structure/find-the-majority-element-that-occurs-more-than-n-2-times/

// Brute Force Approch
// TC -> O(n * n)
// SC -> O(1)

// Thought Process
// 1. Count the frequency of every element.
// 2. Check if it's majority element or not with comparing with n/2.

func majorityElement(_ nums: [Int]) -> Int {
    let n = nums.count

    for i in nums.indices {
        var count = 1
        for j in i+1..<n {
            if nums[i] == nums[j] {
                count += 1
            }
        }

        if count > n / 2 {
            return nums[i]
        }
    }

    return -1
}

// Better Approch

// TC -> O(n) + O(1)
// SC -> if majority elemenet always exists then  O(n/2) else can be upto O(n).

// Thought Process
// 1. In the brute force approch, we are iterating also for repeated elements whose frequency earlier been cheched.
// 2. In order to optimize the brute solution, we will use Dictionary to track the freqencies.

func majorityElement(_ nums: [Int]) -> Int {
    var dict = [Int: Int]()
    let n = nums.count

    for ele in nums {
        if let value = dict[ele] {
            dict[ele]! += 1
        }
        else {
            dict[ele] = 1
        }

         if dict[ele]! > n / 2 {
            return ele
        }
    }

    return -1
}


// Optimal Approch
// TC -> O(n)
// ** if majaority element always exists else you need to check ele frequency is more than n/2 or not by iternating
// whole array once again.

// Thought Process
// 1. We know that majority element's frequency is greater than n/2 times.
// 2. So, we start by couting the frequency of first element if the next element is same as previous, then we will
// increase the frequency else decrease it.
// 3. if frequency reaches to zero, then we change the element with current.
// ** The element with the most occurrence will remain and the rest will cancel themselves.

func majorityElement(_ nums: [Int]) -> Int {
  
  let n = nums.count

  var count = 0
  var major = -1

  for ele in nums {

    if count == 0 {
        major = ele
    }

    if major == ele {
        count += 1
    }
    else {
        count -= 1
    }
  }

  return major
}

A23.swift

// Kadane's Algorithm : Maximum Subarray Sum in an Array ( LC: 53. Maximum Subarray ) 

// Problem Link: https://leetcode.com/problems/maximum-subarray/description/
// Article Link: https://takeuforward.org/data-structure/kadanes-algorithm-maximum-subarray-sum-in-an-array/

// Brute Force Approch
// TC -> O(n * n)
// SC -> O(1)

// Thought Process
// 1. I will generate all the subarray's sum.
// 2. Keep a variable max sum to store the maximum subarray sum.

func maxSubArray(_ nums: [Int]) -> Int {
        
    let n = nums.count

    var mSum = Int.min

    for i in nums.indices {
        var tSum = 0

        for j in i..<n {
            tSum += nums[j]

            if tSum > mSum {
                mSum = tSum
            }
        }
    }

    return mSum
}

// Optimal Approch
// TC-> O(n)
// SC -> O(1)

// Thought Process
// There can be maximum 3 kinds of array, which can contains:
// 1. Positive elements: In these case whole array is subarray with maximum sum.
// 2. Mix of positive and negative elements: Resulted subarray always start with +ve element and always end with +ve elements.
// It will contains only those negative elements whose addition still give us positive sum.
// 3. Only negative elements: Resulted array only contains only one negative element which is greater than others.

func maxSubArray(_ nums: [Int]) -> Int {
        
    let n = nums.count

    var mSum = Int.min, tSum = 0

    for ele in nums {
        tSum += ele
        if tSum > mSum {
            mSum = tSum
        }

        // Helps when your array contains only negative elements and when both ( case: when you encountered an element which 
        // makes your sum negative, then there is no point to consider that element instead you should reset your sum, then start 
        // creating new subarray ).
        if tSum < 0 {
            tSum = 0
        }
    }

    return mSum
}

// Updated version that prints the subarray indexes too

func maxSubArray(_ nums: [Int]) -> Int {
        
    let n = nums.count

    var mSum = Int.min, tSum = 0
    var start = 0, end = 0, tStart = 0

    for i in nums.indices {
        
        // new beginning of subarray.
        if tSum == 0 {
            tStart = i
        }

        tSum += nums[i]

        if tSum > mSum {
            mSum = tSum
            start = tStart
            end = i
        }

        if tSum < 0 {
            tSum = 0
        }
    }

    print("Start: \(start) End: \(end)")

    return mSum
}

A24.java

// Count frequency of each element in the array ( Frequency of limited range elements )

//Question Link: https://www.geeksforgeeks.org/problems/frequency-of-array-elements-1587115620/0
//Video Reference: https://www.youtube.com/watch?v=B2hI-QPoisk

//Optimal Approch
//TC -> O(2N) 
//SC -> O(1)

public static void frequencyCount(int arr[], int N, int P)
{
    int i = 0;

    while(i < N) {
        int index = arr[i];

        if(index > N) {
            arr[i] = 0;
            i++;
            continue;
        }

        if(index > 0) 
        {
            int ele = arr[index - 1];
            if(ele <= 0) {
                arr[index - 1]--;
                arr[i] = 0;
            }
            else {
                arr[i] = ele;
                arr[index - 1] = -1;
            }
        }

        if(arr[i] <= 0) {
            i++;
        }
    }

    for(int j = 0; j < N; j++) {
        if(arr[j] < 0) {
            arr[j] = -arr[j];
        }
    }
}

// Approch - 2 ( Easy )
// TC -> O(3n)
// SC -> O(1)
// Thoughtprocess -> Representing frequency by adding n into the index that represents frequency.

public static void frequencyCount(int arr[], int n, int P)
{
  // Step 1: Remove all the elements which is greater than n. 
    for(int i = 0; i < n; i++) {
        if (arr[i] > n) {
            arr[i] = 0;
        }
    }

  // Step 2: Here arr[i] can be a value which is greater than n when it is representing a frequency.
  // that's why we need to decode first (remove that addition if any) before accessing it.
  
  // Here index can be zero if arr[i] is zero ( arr will contains zero when elements are greater than n,
  // see upper loop code )
  
  // We used n + 1 as an addition element and modulus element instead of n because array can contain
  // n as an element, in that case index will be 0 at line 89 which it should not be.
  
    for(int i = 0; i < n; i++) {
        int index = arr[i] % (n + 1);
        if (index > 0) {
            arr[index - 1] += n + 1;
        }
    }
  
  // Remove additions of n + 1.
    for(int i = 0; i < n; i++) {
        arr[i] = arr[i] / (n + 1);
    }
}

A25.swift

// 121. Best Time to Buy and Sell Stock

//LeetCode: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
// Article Link: https://takeuforward.org/data-structure/stock-buy-and-sell/

// Brute Force Approch
// TC -> O(n*n)
// SC -> O(1)

// Thought Proces:
// 1. I will buy stock every day and will sell stocks every day.

 func maxProfit(_ prices: [Int]) -> Int {
        
    var profit = 0
    let n = prices.count

    for i in prices.indices {
        for j in i+1..<n {
            if prices[j] > prices[i] && prices[j] - prices[i] > profit {
                profit = prices[j] - prices[i]
            }
        }
    }

    return profit
}

// Optimal Approch
// TC -> O(n)
// SC -> O(1)

// Thought Process
// 1. I will buy stocks on first day.
// 2. In the next iteration, check that day price, if it is smaller than my buy day price then I will buy on that day.
// 3. If the new day price are higher than my current buy day price, then if will calculate difference (profit).
// 4. Replce the calculated profit with current profit if it is greater.

func maxProfit(_ prices: [Int]) -> Int {
    var maxProfit = 0

    var minPrice = prices[0]

    for price in prices {
        if price < minPrice {
            minPrice = price
        }
        else {
            maxProfit = max(price - minPrice, maxProfit)
        }
    }

    return maxProfit
}

A26.swift

// Print frequency of each element in the array

// Article Link: https://takeuforward.org/data-structure/count-frequency-of-each-element-in-the-array/

// TC -> O(n * n)
// SC -> O(n)

func printFrequency(arr: [Int]) {
    
    var n = arr.count
    
    var visitedArray = Array<Bool>(repeating: false, count: n)
    
    for i in 0..<n {
        
        if visitedArray[i] == true {
            continue
        }
        
        var count = 1
        
        for j in i + 1..<n {
            if arr[i] == arr[j] {
                count += 1
                visitedArray[j] = true
            }
        }
        
        print("\(arr[i]): \(count)")
    }
}]

// TC -> O(n)
// SC -> O(n)

func printFrequency2(arr: [Int]) {
    var n = arr.count
    
    var dict = [Int: Int]()
    
    for ele in arr {
        
        if let val = dict[ele] {
            dict[ele] = val + 1
        }
        else {
            dict[ele] = 1
        }
    }
    
    print(dict)
}

A27.swift

// 2149. Rearrange Array Elements by Sign 

// Question Link: https://leetcode.com/problems/rearrange-array-elements-by-sign/description/
// Article Link: https://takeuforward.org/arrays/rearrange-array-elements-by-sign/

// Better approch
// TC -> O(n)
// SC -> O(n)

func rearrangeArray(_ nums: [Int]) -> [Int] {
    
    var newArr = Array<Int>(repeating: 0, count: nums.count)

    var even = 0, odd = 1

    for i in nums.indices {
        if nums[i] > 0 {
            newArr[even] = nums[i]
            even += 2
        }
        else {
            newArr[odd] = nums[i]
            odd += 2
        }
    }

    return newArr
}

A28.swift

// 1752. Check if Array Is Sorted and Rotated

// Problem Link: https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/description/

// Better Solution -> O(2n)
// SC -> O(1)
func check(_ nums: [Int]) -> Bool {

    var n = nums.count

    if n == 1 {
        return true
    }

    // Find the smallest element index so that we can get the how much the right rotated array is.
    var si = 0
    for i in 1..<n {
        if nums[si] >= nums[i] && nums[i-1] != nums[i] {
            si = i;
        }
    }
  
  // check array is sorted or not starting from si.
    for i in 0...n-2 {
        if nums[(i + si) % n] > nums[(i + si + 1) % n] {
            return false
        }
    }

    return true
}

// Optimal Solution
// TC -> O(n)
// SC -> O(1)

func check(_ nums: [Int]) -> Bool {

    var n = nums.count

    if n == 1 {
        return true
    }

    // First will find how many times there is break while checking for array is sorted or not.
    var count = 0;

    for i in 0...n-2 {
        if nums[i] > nums[i + 1] {
            count += 1
        }
    }
  
    // Check last element is greater than first increase the count. 
    if nums[n-1] > nums[0] {
        count += 1
    }

    return count <= 1
  }

A29.java

// Max sum in sub-arrays ( 2 ) 

// Problem Link: https://www.geeksforgeeks.org/problems/max-sum-in-sub-arrays0824/0

// Brute Force Approch

// TC -> O(n * n)
// SC -> O(1)

// Thought Process
// 1. I will generate all the sub-arrays.
// 2. Whenever a new element is inserted into the range, check with smallest and second smallest number.
// 3. After adjusting new number, if sum is greater than maxSum then maxSum will be replaced with sum.

public static long pairWithMaxSum(long arr[], long N)
{
    long maxSum = 0;

    for (int i = 0; i < N; i++) {

        long s = Long.MAX_VALUE, ss = Long.MAX_VALUE;

        for (int j = i; j < N; j++) {

            if(arr[j] < s) {
                ss = s;
                s = arr[j];
            }
            else if (arr[j] < ss) {
                ss = arr[j];
            }

            long tSum = s + ss;

            if (tSum > maxSum) {
                maxSum = tSum;
            }
        }
    }

    return maxSum;
}

// Optimal Approch

// TC-> O(n)
// SC-> O(1)

// Observation
// 1. I found that smallest and second smallest number with in range i...j (where i < j) 
// with maximum sum is always contigous (next to one another).

// Thought Process
// 1. According to observation, we only need to find contigous elements whose sum is greater than others contigous elements.

public static long pairWithMaxSum(long arr[], long N)
{
    long maxSum = 0;

    for (int i = 0; i <= N - 2; i++) {
        long tSum = arr[i] + arr[i + 1];
        if(tSum > maxSum) {
            maxSum = tSum;
        }
    }

    return maxSum;
}

A30.swift

// next_permutation : find next lexicographically greater permutation ( 31. Next Permutation ) ( Not revised )

// Problem link: https://leetcode.com/problems/next-permutation/description/
// Article Link: https://takeuforward.org/data-structure/next_permutation-find-next-lexicographically-greater-permutation/

// Optimal Approch
// TC -> O(n + n + n/2 - 2)
// SC -> O(1)

func nextPermutation(_ arr: inout [Int]) {
    
    let n = arr.count

    var index = -1

    // Find an element which breaks the descending order, if not able to find ( because there is no permutation 
    // greater than current ) just reverse the array .
    // Starting from last so that if we found an index, we are sure that all the element are right to that index
    // is in descending order.
    
    for i in stride(from: n - 2, to: -1, by: -1) {
        if arr[i] < arr[i + 1] {
            index = i
            break
        }
    }

    if index == -1 {
        reverse(&arr, 0, n - 1)
        return
    }

    // find the element that just greater than index element, because 
    // next permutation is just greater than current not extreme.

    // we know that array is in descending order (in range from index + 1 to n-1)
    // we start from last to index + 1 ( so that we can place index to correct position while maintaining descending order)

    for i in stride(from: n-1, to: index, by: -1) {
        if (arr[i] > arr[index]) {
            arr.swapAt(i, index)
            break
        }
    }

    // reverse the array, so that we can formed possible smallest number starting with index.
    reverse(&arr, index+1, n-1)
}

func reverse(_ arr: inout [Int], _ start: Int, _ end: Int) {
    var i = start, j = end
    while(i < j) {
        arr.swapAt(i, j)
        i += 1
        j -= 1
    }
}


// Example: [2, 1, 5, 4, 3, 0, 0]
// After first loop we got index = 1 ( this is element's index which breaks the descending order )
// n = 7
// number which is just greater than 1 in the range (index + 1..<n) is 3
// swap it with index (1)
// resulted array after second iteration of loop: [2, 3, 5, 4, 1, 0, 0]

// sort the array in assending order (reverse) to formed possible smallest number in range (index + 1, n - 1)
// resulted array: [2, 3, 0, 0, 1, 4, 5]

A31.swift

// Leaders in an Array (GFG: Array Leaders)

// Article Link: https://takeuforward.org/data-structure/leaders-in-an-array/
// Problem Link: https://www.geeksforgeeks.org/problems/leaders-in-an-array-1587115620/1

// Brute Force Approch
// TC -> O(n * n)
// SC -> O(n) <- (Used to return the result, not the solve the problem)

// Thought Process
// We will traverse the array from left to right and check every element if it is greater than all the elements 
// on the right side or not.
// If it is consider that element as leader and add it into the list.

func leaders(_ arr: [Int]) -> [Int] {
    
    var result = [Int]()
    let n = arr.count
    for i in arr.indices {
        var leader = true
        
        for j in i+1..<n {
            if arr[i] < arr[j] {
                leader = false
                break
            }
        }
        
        if leader {
            result.append(arr[i])
        }
    }
    
    return result
}

// Optimal Approch
// TC -> O(n + n/2)
// SC -> O(n) <- (Used to return the result, not the solve the problem)

// Thought Process:
// We will starting from n-1 to 0 range and add last element into the result list.
// And hold that last element into variable 'ele' if someone is greater than ele, then add them into list.
// Always store that greater element in ele variable.
// Repeat the steps.

func leaders(_ arr: [Int]) -> [Int] {
    
    var result = [Int]()
    let n = arr.count
    
    var ele = Int.min
    
    for i in stride(from: n-1, to: -1, by: -1) {
        if ele <= arr[i] {
            ele = arr[i]
            result.append(ele)
        }
    }
    
    result.reverse()
    
    return result
}

A32.swift

// Longest Consecutive Sequence in an Array

// Article Link: https://takeuforward.org/data-structure/longest-consecutive-sequence-in-an-array/
// Problem Link: https://leetcode.com/problems/longest-consecutive-sequence/

// Brute Force Approch

// TC -> O(n * n * n)
// SC -> O(1)

// Thought Process
// 1. First, we will try to find one greater element for every element using binary search.
// 2. If found, then increase the ele by 1 and counter, try to find this new element.
// 3. Repeat.

func longestConsecutive(_ arr: [Int]) -> Int {
    let n = arr.count
    var maxLength = 0

    for i in arr.indices {
        var ele = arr[i] + 1
        var count = 1

        while(binarySearch(arr, ele)) {
            ele += 1
            count += 1
        }

        maxLength = max(maxLength, count)
    }

    return maxLength
}

func binarySearch(_ arr: [Int], _ number: Int) -> Bool {
    for ele in arr {
        if ele == number {
            return true
        }
    }

    return false
}

// Better Approch V1

// TC -> O(nlogn * n)
// SC -> O(n)

// Thought Process:
// 1. First we sort the array.
// 2. Keeping a track of last smallest element.
// 3. If arr[i] - 1 == lastSmallest element then arr[i] will be the part of sequence.
//    if it is part of sequence increase the counter and change lastSmallest element to current.
// 4. If arr[i] == lastSmallest we will nothing.
// 5. if arr[i] != lastSmallest, we will reset the variables.

func longestConsecutive(_ nums: [Int]) -> Int {
    var arr = nums
    arr.sort()

    let n = arr.count
    var maxLength = 0, currentCount = 1, lastSmallest = Int.min

    for ele in arr {
        if ele - 1 == lastSmallest {
            currentCount += 1
            lastSmallest = ele
        }
        else if ele != lastSmallest {
            currentCount = 1
            lastSmallest = ele
        }

        maxLength = max(maxLength, currentCount)
    }

    return maxLength
}

// Better Approch V2 

// Easy.

func longestConsecutive(_ nums: [Int]) -> Int {

    if nums.count <= 1 {
        return nums.count
    }

    var arr = nums
    arr.sort()

    var length = 1, maxLength = 1

    let end = arr.count - 2

    for i in 0...end {
        if arr[i] + 1 == arr[i + 1] {
            length += 1
        }
        else if arr[i] != arr[i + 1] {
            length = 1
        }

        maxLength = max(length, maxLength)
    }

    return maxLength;
}


// Optimal Approch 
// TC -> O(n + n)
// SC -> O(n)

// Thought Process:
// We will using the powers of Set to optimize the brute force approch
// 1. First we will add all elements in the set. (It will remove any duplicates, it will beneficial to optimize because
// it will also remove duplicates of first element of our consecutive sequence.)
// 2. We will check if ele - 1 is exists in set, we don't go further (simply skip that element)
// 3. If not check every concesutive elements like brute force solution.

func longestConsecutive(_ nums: [Int]) -> Int {

    let n = nums.count

    var set = Set(nums)

    var maxLength = 0

    for ele in set {
        if set.contains(ele - 1) == false {
            var currentCount = 1
            var x = ele + 1

            while(set.contains(x)) {
                currentCount += 1
                x += 1
            }

            maxLength = max(maxLength, currentCount)
        }
    }

    return maxLength
}

A33.swift

// Title:  Set Matrix Zeroes
// Problem Statement: Given a matrix if an element in the matrix is 0 then you will have to set its entire column and row to 0 and then return the matrix.


// Article Link: https://takeuforward.org/data-structure/set-matrix-zero/
// Question Link: https://leetcode.com/problems/set-matrix-zeroes/description/

// Brute Force Approach

// Thought Process -> Maintain a copy of the array. 
// Use the duplicate array for traversing and original array for mutating.

// TC -> O(n * m) * O(n + m)
// SC -> O(n * m)

func setZeroesBrute(_ matrix: inout [[Int]]) {
    
    let tempMatrix = matrix
    
    let rowsCount = tempMatrix.count
    let colsCount = tempMatrix[0].count
    
    // 1. Find the zero in the matrix
    for rowIndex in tempMatrix.indices {
        for colIndex in tempMatrix[rowIndex].indices {
            if tempMatrix[rowIndex][colIndex] == 0 {
                
                // 2. Mark all the row elements to zeros
                for i in 0..<colsCount {
                    matrix[rowIndex][i] = 0
                }
                
                // 3. Mark all the col elements to zeros
                for i in 0..<rowsCount {
                    matrix[i][colIndex] = 0
                }
            }
        }
    }
}

// Best Approach

// Thought Process: Track the rows and cols that needs to be mark as zero.
// Iterate the whole array again, mark the rows and cols to zero which you tracked.

// TC -> O(n * m) + O(n * m)
// SC -> O(n + m)
func setZeroesBest(_ matrix: inout [[Int]]) {
    
    let rowsCount = matrix.count
    let colsCount = matrix[0].count
    
    var faultyRows = Array<Int>(repeating: 0, count: rowsCount)
    var faultyCols = Array<Int>(repeating: 0, count: colsCount)
    
    // 1. Find the zero in the matrix and add them into the set.
    for rowIndex in matrix.indices {
        for colIndex in matrix[rowIndex].indices {
            if matrix[rowIndex][colIndex] == 0 {
                faultyRows[rowIndex] = 1
                faultyCols[colIndex] = 1
            }
        }
    }
    
    // 2. Marking zero
    for rowIndex in matrix.indices {
        for colIndex in matrix[rowIndex].indices {
            if faultyRows[rowIndex] == 1 || faultyCols[colIndex] == 1{
                matrix[rowIndex][colIndex] = 0
            }
        }
    }
}

// Optimal Approach
// Track the cols and rows which needs to be marked as zero inside the matrix.

// TC -> O(n * m) + O(n * m) + O(n) + O(m)
// SC -> O(1)

func setZeroes(_ matrix: inout [[Int]]) {

        // matrix[0][0] will be used to know whether we need to mark whole first row as zero or not.
        // so for the column zero we also need something that's why we used a variable.
        var colFirst = 1
        
        let rowsCount = matrix.count
        let colsCount = matrix[0].count
        
        // Tracking which whole row and column need to marked as zero in matrix itself.
        for rowIndex in matrix.indices {
            for colIndex in matrix[rowIndex].indices {
                if matrix[rowIndex][colIndex] == 0 {
                    matrix[rowIndex][0] = 0
                    
                    if colIndex == 0 {
                        colFirst = 0
                    }
                    else {
                        matrix[0][colIndex] = 0
                    }
                }
            }
        }
        
        // Marking zero but leaving first row and first column.
        for rowIndex in matrix.indices {
            for colIndex in matrix[rowIndex].indices {
                if colIndex != 0 && rowIndex != 0 {
                    if matrix[rowIndex][0] == 0 || matrix[0][colIndex] == 0 {
                        matrix[rowIndex][colIndex] = 0
                    }
                }
            }
        }
        
        // Deciding whether we need to mark first row as zero or not.
        if matrix[0][0] == 0 {
            for col in matrix[0].indices {
                matrix[0][col] = 0
            }
        }
        
        // Deciding whether we need to mark first col as zero or not.
        if colFirst == 0 {
            for row in matrix.indices {
                matrix[row][0] = 0
            }
        }

        // Make sure you mark first row as zero (if required) then go for first column.
    }

A34.swift

// Rotate Image
// LeetCode: https://leetcode.com/problems/rotate-image/

// Brute Force Approach:

// Observation:

// Consider this example:

/**
     Question            Solution

    | 1, 2, 3 |        | 7, 4, 1 |   
    | 4, 5, 6 |   =>   | 8, 5, 2 |
    | 7, 8, 9 |        | 9, 6, 3 |

          i, j           i, j
    1 -> (0, 0)         (0, 2)
    2 -> (0, 1)   ->    (1, 2)
    3 -> (0, 2)         (2, 2)

    
    Qustion colIndex(j) is answer rowIndex(i) and question's rowIndex(i) can be used to generate answer column index with formula
    (n - 1) - question's rowIndex.

    Using above observation you can place elements at its 90 degree clockwise rotated position.
*/

// TC -> O(m * n)
// SC -> O(m * n)

// Because in the question given m == n then you can say
// TC -> O(n * n)
// SC -> O(n * n)


func rotateImage(matrix: inout [[Int]]) {
    
    let n = matrix.count
    var tempMatrix = matrix
    
    for rowIndex in tempMatrix.indices {
        for colIndex in tempMatrix[rowIndex].indices {
            let myRow = colIndex
            let myCol = (n - 1) - rowIndex
            matrix[myRow][myCol] = tempMatrix[rowIndex][colIndex]
        }
    }
}

// Optimal Approach -> O(n * n) + O(n * n)
// SC -> O (1)

func rotateImageOptimal(matrix: inout [[Int]]) {
    
    let n = matrix.count
    
    // 1. Transpose
    
    for row in matrix.indices {
        for col in matrix[row].indices where row < col {
            (matrix[row][col], matrix[col][row]) = (matrix[col][row], matrix[row][col])
        }
    }
    
    // Reverse
    for row in matrix.indices {
        for col in matrix[row].indices where col < matrix[row].count / 2 {
            (matrix[row][col], matrix[row][n - 1 - col]) = (matrix[row][n - 1 - col], matrix[row][col])
        }
    }
}

A35.swift

// Program: https://leetcode.com/problems/spiral-matrix/


// TC -> O(m * n)
// SC -> O(m * n)

// As we are traversing every element in the array, using the approach right -> bottom -> left -> top
// And constant elements inside every loop => For this case left -> right, top is contant element for the row, and
// in next left -> right tranversal should happen in the next row.

func spiralOrder(_ arr: [[Int]]) -> [Int] {
        let m = arr.count
        let n = arr[0].count
        let linearArraySize = m * n
        var linearArray = Array(repeating: 0, count: linearArraySize)
        var index = 0
        
        var top = 0, left = 0, right = n - 1, bottom = m - 1

        while(index < linearArraySize) {
            
            // right
            for i in stride(from: left, to: right + 1, by: 1) {
                linearArray[index] = arr[top][i]
                index += 1
            }
            top += 1
            
            // bottom
            for i in stride(from: top, to: bottom + 1, by: 1) {
                linearArray[index] = arr[i][right]
                index += 1
            }
            right -= 1
        
            // left
            // Think condition for the case [1, 2, 3, 4]
            if top <= bottom {
                for i in stride(from: right, to: left - 1, by: -1) {
                    linearArray[index] = arr[bottom][i]
                    index += 1
                }
                bottom -= 1
            }
        
            if left <= right {
                // top
                // Think condition for the case [[1],[2],[3]]
                for i in stride(from: bottom, to: top - 1, by: -1) {
                    linearArray[index] = arr[i][left]
                    index += 1
                }
                left += 1
            }
        }
    
        return linearArray
    }

A36.swift

// https://leetcode.com/problems/subarray-sum-equals-k/submissions/
// 560. Subarray Sum Equals K

// Brute Force Approach

// TC -> O(n * n)
// SC -> O(1)

// ThoughtProcess -> Generate all the subarrays whose sum == k and count them.

func subarraySum(_ nums: [Int], _ k: Int) -> Int {

    var count = 0
    let n = nums.count
    for i in nums.indices {
        var sum = 0
        for j in i..<n {
            sum += nums[j]

            if sum == k {
                count += 1
            }
        }
    }
    return count
}

A37.swift

// Pascal traingle

func generate(_ numRows: Int) -> [[Int]] {
    
    var result = [[1]]
    result.reserveCapacity(numRows)
    
    for i in 1..<numRows {
        let arr = result[i - 1]
        var newArr = [Int](repeating: 1, count: arr.count + 1)

        for j in stride(from: 1, to: (arr.count/2) + 1, by: 1) {
            newArr[j] = arr[j - 1] + arr[j]
            newArr[newArr.count - 1 - j] = newArr[j]
        }
        result.append(newArr)
    }
    
    return result
}

A7.java

// Find GCD OR HCF of two numbers | A7.java

// Problem Link: https://www.geeksforgeeks.org/problems/lcm-and-gcd4516/1
// Article Link: https://takeuforward.org/data-structure/find-gcd-of-two-numbers/

// Brute Force Approach

// TC -> O(min(n,m))
// Best Case TC -> O(1)

public static int calcGCD(int n, int m) {
    
    int min = n < m ? n : m;

    int gcd = 1;

    for(int i = min; i > 1; i--) {
        if(n % i == 0 && m % i == 0) {
            return i;
        }
    }

    return gcd;
}

// Optimal Approach - 1

// Formula gcd(a, b) = gcd(a-b, b) where a > b

// Thought Process
// We will apply above formula again and again util one of them element will become 0.
// And return the non zero element ( which is your HCF )

public static int gcd(int a, int b) {
    while(a > 0 && b > 0) {
        if (a > b) {
            a = a - b;
        }
        else {
            b = b - a;
        }
    }

    return a != 0 ? a : b;
}

// Optimal Approach - 2

// TC -> O(log(fi)(min(n,m)))
// log base is fi because divisor is dynamic.

// Exclusively by Striver
// Use new formula gcd(a, b) = gcd(a % b, b) where a > b

public static int gcd(int a, int b) {
    while(a > 0 && b > 0) {
        if (a > b) {
            a = a % b;
        }
        else {
            b = b % a;
        }
    }

    return a != 0 ? a : b;
}

A8.java

// Brute + Better + Optimal !

// Brute = Sort array and find the minimum !

// Second Largest number in the array !

int print2largest(int arr[], int n) {

        // I'm using Bubble Sort.
        for(int i = 0; i <= n - 2; i++) 
        {
            boolean didSwapHappen = false;
            
            for(int j = 0; j <= n - 2 - i; j++) 
            {
                if(arr[j] > arr[j+1]) {
                    didSwapHappen = true;
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            
            if(didSwapHappen == false) {
                break;
            }
        }
        
        for(int i = n - 2; i >= 0; i--) {
            if(arr[i] != arr[n-1]) {
                return arr[i];
            }
        }
        
        return -1;
    }

// Better Approch 

int print2largest(int arr[], int n) {
        
        if(n == 2) {
            
            if(arr[0] == arr[1]) 
                return -1;
                
            return arr[0] > arr[1] ? arr[1] : arr[0];
        }
        
        int largest = arr[0];

        for(int i = 1; i < n; i++) {
            if(arr[i] > largest) {
                largest = arr[i];
            }
        }

        int secondLargest = -1;

        for (int i = 1; i < n; i++) {
            if(arr[i] > secondLargest && arr[i] != largest) {
                secondLargest = arr[i];
            }
        }

        return secondLargest;
    }
    
    
    // Optimal Approch:
    int print2largest(int arr[], int n) {
        
        int largest = arr[0];
        int secondLargest = -1;
        
        for(int i = 1; i < n; i++) 
        {
            if(arr[i] > largest) {
                secondLargest = largest;
                largest = arr[i];
            } else if(arr[i] > secondLargest && arr[i] != largest) {
                secondLargest = arr[i];
            }
        }
        
        return secondLargest;
    }

A9.swift

// Find three large numbers from Array in ascending order. | A9.swift

func findThreeLargeNumbers(from numberArray: [Int]) -> [Int] {
    guard !numberArray.isEmpty, numberArray.count > 2 else {
        return []
    }
    
    var resultArray = Array(repeatElement(Int.min, count: 3))
    
    for number in numberArray {
        
        let indexToBeInserted: Int
        
        if number > resultArray[2] {
            indexToBeInserted = 2
        }
        else if number > resultArray[1] {
            indexToBeInserted = 1
        }
        else if number > resultArray[0] {
            indexToBeInserted = 0
        }
        else {
            indexToBeInserted = -1
        }
        
        if indexToBeInserted > 0 {
            var current = indexToBeInserted
            
            // Truncation always occurs from left, left most element will be removed whenever we found index > -1
            while current > 0 {
                swapNumbers(indexA: current - 1, indexB: indexToBeInserted, from: &resultArray)
                current -= 1
            }
            resultArray[indexToBeInserted] = number
        }
    }
    
    return resultArray
}

func swapNumbers(indexA: Int, indexB: Int, from array: inout [Int]) {
    let temp = array[indexA]
    array[indexA] = array[indexB]
    array[indexB] = temp
}


let numberArray = [5, 111, 110, 2, 6]
let largeNumbers = findThreeLargeNumbers(from: numberArray)
print(largeNumbers)