DSA Problem and Solutions on Array

DSA Interview Questions on Array

An array is a data structure that can store a fixed-size sequence of elements of the same type. It is a collection of items stored at contiguous memory locations, and it is used to represent a collection of similar items. Arrays are commonly used in programming and are fundamental for managing collections of data.

Key Characteristics of Arrays

1. Fixed Size: The size of an array is defined at the time of creation and cannot be changed during runtime.
2. Homogeneous Elements: All elements in an array must be of the same data type (e.g., integers, floats, strings).
3. Index-Based Access: Elements in an array can be accessed using their index, which starts at 0. This allows for fast access and manipulation of elements.
4. Contiguous Memory Allocation: Elements are stored in contiguous memory locations, which makes accessing elements efficient.

Types of Arrays

1. One-Dimensional Array: A linear list of elements.
   • Example:int arr[] = {1, 2, 3, 4};
2. Multi-Dimensional Array: An array of arrays, often used to represent matrices or grids.
   • Example: int matrix[][] = {{1, 2}, {3, 4}};

Use Cases of Arrays

• Storing Data: Arrays are commonly used to store collections of data, such as lists of numbers or objects.
• Implementing Algorithms: Many algorithms (like sorting and searching) utilize arrays as their primary data structure.
• Matrices and Tables: Arrays can represent mathematical matrices or database tables.

Find the maximum element in an array

Algorithm:

1. Initialize a variable max to the first element of the array.
2. Iterate through the array starting from the second element.
3. Compare each element with max and update max if the element is greater.
4. Return max after the iteration completes.

#include <iostream>
#include <vector>
#include <algorithm>

int findMax(const std::vector<int>& arr) {
    return *std::max_element(arr.begin(), arr.end());
}

int main() {
    std::vector<int> arr = {1, 5, 3, 9, 2};
    std::cout << "Maximum element is " << findMax(arr) << std::endl;
    return 0;
}

import java.util.Collections;
import java.util.List;

public class Main {
    public static int findMax(List<Integer> list) {
        return Collections.max(list);
    }

    public static void main(String[] args) {
        List<Integer> list = List.of(1, 5, 3, 9, 2);
        System.out.println("Maximum element is " + findMax(list));
    }
}

def find_max(arr):
    return max(arr)

Reverse an array

Algorithm:

1. Initialize two pointers, start at the beginning (index 0) and end at the end (last index) of the array.
2. Swap the elements at start and end.
3. Increment start and decrement end.
4. Repeat steps 2 and 3 until start is greater than or equal to end.

#include <iostream>
#include <vector>
#include <algorithm>

void reverseArray(std::vector<int>& arr) {
    std::reverse(arr.begin(), arr.end());
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5};
    reverseArray(arr);
    for(int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void reverseArray(List<Integer> list) {
        Collections.reverse(list);
    }

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
        reverseArray(list);
        for (int num : list) {
            System.out.print(num + " ");
        }
    }
}

def reverse_array(arr):
    return arr[::-1]

Find the minimum element in a rotated sorted array

Algorithm:

1. Use binary search to find the pivot point where the rotation occurred.
2. The minimum element is the element just after the pivot.

#include <iostream>
#include <vector>

int findMin(const std::vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) left = mid + 1;
        else right = mid;
    }
    return nums[left];
}

int main() {
    std::vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    std::cout << "Minimum element is " << findMin(nums) << std::endl;
    return 0;
}

public class Main {
    public static int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 6, 7, 0, 1, 2};
        System.out.println("Minimum element is " + findMin(nums));
    }
}

def find_min_rotated(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        mid = (left + right) // 2
        if arr[mid] > arr[right]:
            left = mid + 1
        else:
            right = mid
    return arr[left]

Find the “Kth” max and min element of an array

Algorithm:

1. Sort the array.
2. The Kth minimum element is at index K-1.
3. The Kth maximum element is at index n-K, where n is the length of the array.

#include <iostream>
#include <vector>
#include <algorithm>

int findKthMax(std::vector<int>& arr, int k) {
    std::sort(arr.begin(), arr.end(), std::greater<int>());
    return arr[k - 1];
}

int findKthMin(std::vector<int>& arr, int k) {
    std::sort(arr.begin(), arr.end());
    return arr[k - 1];
}

int main() {
    std::vector<int> arr = {7, 10, 4, 3, 20, 15};
    int k = 3;
    std::cout << k << "rd largest element is " << findKthMax(arr, k) << std::endl;
    std::cout << k << "rd smallest element is " << findKthMin(arr, k) << std::endl;
    return 0;
}

import java.util.Arrays;

public class Main {
    public static int findKthMax(int[] arr, int k) {
        Arrays.sort(arr);
        return arr[arr.length - k];
    }

    public static int findKthMin(int[] arr, int k) {
        Arrays.sort(arr);
        return arr[k - 1];
    }

    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 3;
        System.out.println(k + "rd largest element is " + findKthMax(arr, k));
        System.out.println(k + "rd smallest element is " + findKthMin(arr, k));
    }
}

def kth_max_min(arr, k):
    sorted_arr = sorted(arr)
    kth_max = sorted_arr[-k]
    kth_min = sorted_arr[k - 1]
    return kth_max, kth_min

Move all negative numbers to beginning and positive to end with constant extra space

Algorithm:

1. Use two pointers, one starting at the beginning and one at the end of the array.
2. Increment the beginning pointer until you find a positive number.
3. Decrement the end pointer until you find a negative number.
4. Swap these two numbers.
5. Repeat steps 2-4 until the beginning pointer is greater than the end pointer.

#include <iostream>
#include <vector>

void rearrange(std::vector<int>& arr) {
    int j = 0;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] < 0) {
            if (i != j) std::swap(arr[i], arr[j]);
            j++;
        }
    }
}

int main() {
    std::vector<int> arr = {-1, 2, -3, 4, -5, 6, -7, 8, 9};
    rearrange(arr);
    for (int num : arr) {
        std::cout << num << " ";
    }
    return 0;
}

import java.util.Arrays;

public class Main {
    public static void rearrange(int[] arr) {
        int j = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) {
                if (i != j) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {-1, 2, -3, 4, -5, 6, -7, 8, 9};
        rearrange(arr);
        System.out.println(Arrays.toString(arr));
    }
}

def rearrange_negatives(arr):
    j = 0  # Pointer for the next negative position
    for i in range(len(arr)):
        if arr[i] < 0:
            arr[j], arr[i] = arr[i], arr[j]
            j += 1
    return arr

Find the Union and Intersection of two sorted arrays

Union Algorithm:

1. Initialize two pointers, i and j, starting at the beginning of both arrays.
2. Compare elements at i and j.
3. Add the smaller element to the result and move the corresponding pointer.
4. If elements are equal, add it to the result and move both pointers.
5. Add remaining elements from both arrays.

Intersection Algorithm:

1. Initialize two pointers, i and j, starting at the beginning of both arrays.
2. Compare elements at i and j.
3. If elements are equal, add it to the result and move both pointers.
4. If the element in the first array is smaller, move the pointer in the first array.
5. If the element in the second array is smaller, move the pointer in the second array.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

std::vector<int> findUnion(const std::vector<int>& arr1, const std::vector<int>& arr2) {
    std::set<int> s;
    s.insert(arr1.begin(), arr1.end());
    s.insert(arr2.begin(), arr2.end());
    return std::vector<int>(s.begin(), s.end());
}

std::vector<int> findIntersection(const std::vector<int>& arr1, const std::vector<int>& arr2) {
    std::vector<int> intersection;
    std::set<int> s1(arr1.begin(), arr1.end());
    for (int num : arr2) {
        if (s1.count(num)) {
            intersection.push_back(num);
        }
    }
    return intersection;
}

int main() {
    std::vector<int> arr1 = {1, 3, 4, 5, 7};
    std::vector<int> arr2 = {2, 3, 5, 6};
    std::vector<int> unionArr = findUnion(arr1, arr2);
    std::vector<int> intersectionArr = findIntersection(arr1, arr2);

    std::cout << "Union: ";
    for (int num : unionArr) {
        std::cout << num << " ";
    }

    std::cout << "\nIntersection: ";
    for (int num : intersectionArr) {
        std::cout << num << " ";
    }

    return 0;
}

import java.util.*;

public class Main {
    public static List<Integer> findUnion(int[] arr1, int[] arr2) {
        Set<Integer> set = new HashSet<>();
        for (int num : arr1) set.add(num);
        for (int num : arr2) set.add(num);
        return new ArrayList<>(set);
    }

    public static List<Integer> findIntersection(int[] arr1, int[] arr2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> intersection = new HashSet<>();
        for (int num : arr1) set1.add(num);
        for (int num : arr2) {
            if (set1.contains(num)) {
                intersection.add(num);
            }
        }
        return new ArrayList<>(intersection);
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 4, 5, 7};
        int[] arr2 = {2, 3, 5, 6};

        List<Integer> union = findUnion(arr1, arr2);
        List<Integer> intersection = findIntersection(arr1, arr2);

        System.out.println("Union: " + union);
        System.out.println("Intersection: " + intersection);
    }
}

def union_and_intersection(arr1, arr2):
    union = sorted(set(arr1) | set(arr2))
    intersection = sorted(set(arr1) & set(arr2))
    return union, intersection

Find the contiguous sub-array with the maximum sum (Kadane’s Algorithm)

Algorithm:

1. Initialize two variables, max_so_far and max_ending_here, to 0.
2. Iterate through the array.
3. Update max_ending_here by adding the current element.
4. If max_ending_here is greater than max_so_far, update max_so_far.
5. If max_ending_here is less than 0, reset it to 0.
6. Return max_so_far.

#include <iostream>
#include <vector>
#include <climits>

int maxSubArraySum(const std::vector<int>& nums) {
    int max_so_far = INT_MIN, max_ending_here = 0;
    for (int num : nums) {
        max_ending_here = max_ending_here + num;
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}

int main() {
    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    std::cout << "Maximum subarray sum is " << maxSubArraySum(nums) << std::endl;
    return 0;
}

public class Main {
    public static int maxSubArraySum(int[] nums) {
        int maxSoFar = Integer.MIN_VALUE, maxEndingHere = 0;
        for (int num : nums) {
            maxEndingHere = maxEndingHere + num;
            if (maxSoFar < maxEndingHere)
                maxSoFar = maxEndingHere;
            if (maxEndingHere < 0)
                maxEndingHere = 0;
        }
        return maxSoFar;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum subarray sum is " + maxSubArraySum(nums));
    }
}

def max_subarray_sum(arr):
    max_ending_here = max_so_far = arr[0]
    for x in arr[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Find the duplicate number on a given array of n+1 integers

Algorithm:

1. Use Floyd’s Tortoise and Hare (Cycle Detection) to find the duplicate.
2. Initialize two pointers, slow and fast, to the start of the array.
3. Move slow by one step and fast by two steps.
4. When they meet, initialize another pointer to the start.
5. Move both pointers by one step until they meet again.
6. The meeting point is the duplicate number.

#include <iostream>
#include <vector>

int findDuplicate(std::vector<int>& nums) {
    int slow = nums[0];
    int fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    fast = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

int main() {
    std::vector<int> nums = {1, 3, 4, 2, 2};
    std::cout << "Duplicate number is " << findDuplicate(nums) << std::endl;
    return 0;
}

public class Main {
    public static int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        fast = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 2, 2};
        System.out.println("Duplicate number is " + findDuplicate(nums));
    }
}

def find_duplicate(arr):
    slow = fast = arr[0]
    while True:
        slow = arr[slow]
        fast = arr[arr[fast]]
        if slow == fast:
            break
    slow = arr[0]
    while slow != fast:
        slow = arr[slow]
        fast = arr[fast]
    return slow

Merge two sorted arrays without using extra space

Algorithm:

1. Start from the end of both arrays.
2. Compare elements from both arrays.
3. Place the larger element at the end of the first array.
4. Move the pointers and repeat until all elements are merged.

#include <iostream>
#include <vector>
#include <algorithm>

void merge(std::vector<int>& arr1, std::vector<int>& arr2) {
    int m = arr1.size();
    int n = arr2.size();

    for (int i = n - 1; i >= 0; i--) {
        int j, last = arr1[m - 1];
        for (j = m - 2; j >= 0 && arr1[j] > arr2[i]; j--)
            arr1[j + 1] = arr1[j];

        if (j != m - 2 || last > arr2[i]) {
            arr1[j + 1] = arr2[i];
            arr2[i] = last;
        }
    }
}

int main() {
    std::vector<int> arr1 = {1, 3, 5, 7};
    std::vector<int> arr2 = {2, 4, 6, 8};

    merge(arr1, arr2);

    for (int num : arr1) {
        std::cout << num << " ";
    }
    for (int num : arr2) {
        std::cout << num << " ";
    }

    return 0;
}

import java.util.Arrays;

public class Main {
    public static void merge(int[] arr1, int[] arr2) {
        int m = arr1.length;
        int n = arr2.length;

        for (int i = n - 1; i >= 0; i--) {
            int j, last = arr1[m - 1];
            for (j = m - 2; j >= 0 && arr1[j] > arr2[i]; j--)
                arr1[j + 1] = arr1[j];

            if (j != m - 2 || last > arr2[i]) {
                arr1[j + 1] = arr2[i];
                arr2[i] = last;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7};
        int[] arr2 = {2, 4, 6, 8};

        merge(arr1, arr2);

        System.out.println(Arrays.toString(arr1));
        System.out.println(Arrays.toString(arr2));
    }
}

def merge_sorted_arrays(arr1, arr2):
    m, n = len(arr1), len(arr2)
    i, j, k = m - 1, n - 1, m + n - 1
    arr1.extend([0]*n)  # Extend arr1 to hold arr2's elements
    while j >= 0:
        if i >= 0 and arr1[i] > arr2[j]:
            arr1[k] = arr1[i]
            i -= 1
        else:
            arr1[k] = arr2[j]
            j -= 1
        k -= 1
    return arr1

Find the “Kth” largest element in an array

1. Use a min-heap to keep track of the K largest elements.
2. Iterate through the array.
3. Add the current element to the heap.
4. If the heap size exceeds K, remove the smallest element.
5. The root of the heap is the Kth largest element.

#include <iostream>
#include <vector>
#include <queue>

int findKthLargest(std::vector<int>& nums, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    for (int num : nums) {
        minHeap.push(num);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    return minHeap.top();
}

int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;
    std::cout << "Kth largest element is " << findKthLargest(nums, k) << std::endl;
    return 0;
}

import java.util.PriorityQueue;

public class Main {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        System.out.println("Kth largest element is " + findKthLargest(nums, k));
    }
}

import heapq

def kth_largest(arr, k):
    return heapq.nlargest(k, arr)[-1]