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
- Fixed Size: The size of an array is defined at the time of creation and cannot be changed during runtime.
- Homogeneous Elements: All elements in an array must be of the same data type (e.g., integers, floats, strings).
- 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.
- Contiguous Memory Allocation: Elements are stored in contiguous memory locations, which makes accessing elements efficient.
Types of Arrays
- One-Dimensional Array: A linear list of elements.
- Example:int arr[] = {1, 2, 3, 4};
- Multi-Dimensional Array: An array of arrays, often used to represent matrices or grids.
- Example:
int matrix[][] = {{1, 2}, {3, 4}};
- Example:
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:
- Initialize a variable max to the first element of the array.
- Iterate through the array starting from the second element.
- Compare each element with max and update max if the element is greater.
- Return max after the iteration completes.
- C++
- Java
- Python
#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:
- Initialize two pointers, start at the beginning (index 0) and end at the end (last index) of the array.
- Swap the elements at start and end.
- Increment start and decrement end.
- Repeat steps 2 and 3 until start is greater than or equal to end.
- C++
- Java
- Python
#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:
- Use binary search to find the pivot point where the rotation occurred.
- The minimum element is the element just after the pivot.
- C++
- Java
- Python
#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:
- Sort the array.
- The Kth minimum element is at index K-1.
- The Kth maximum element is at index n-K, where n is the length of the array.
- C++
- Java
- Python
#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:
- Use two pointers, one starting at the beginning and one at the end of the array.
- Increment the beginning pointer until you find a positive number.
- Decrement the end pointer until you find a negative number.
- Swap these two numbers.
- Repeat steps 2-4 until the beginning pointer is greater than the end pointer.
- C++
- Java
- Python
#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:
- Initialize two pointers, i and j, starting at the beginning of both arrays.
- Compare elements at i and j.
- Add the smaller element to the result and move the corresponding pointer.
- If elements are equal, add it to the result and move both pointers.
- Add remaining elements from both arrays.
Intersection Algorithm:
- Initialize two pointers, i and j, starting at the beginning of both arrays.
- Compare elements at i and j.
- If elements are equal, add it to the result and move both pointers.
- If the element in the first array is smaller, move the pointer in the first array.
- If the element in the second array is smaller, move the pointer in the second array.
- C++
- Java
- Python
#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:
- Initialize two variables, max_so_far and max_ending_here, to 0.
- Iterate through the array.
- Update max_ending_here by adding the current element.
- If max_ending_here is greater than max_so_far, update max_so_far.
- If max_ending_here is less than 0, reset it to 0.
- Return max_so_far.
- C++
- Java
- Python
#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:
- Use Floyd’s Tortoise and Hare (Cycle Detection) to find the duplicate.
- Initialize two pointers, slow and fast, to the start of the array.
- Move slow by one step and fast by two steps.
- When they meet, initialize another pointer to the start.
- Move both pointers by one step until they meet again.
- The meeting point is the duplicate number.
- C++
- Java
- Python
#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:
- Start from the end of both arrays.
- Compare elements from both arrays.
- Place the larger element at the end of the first array.
- Move the pointers and repeat until all elements are merged.
- C++
- Java
- Python
#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
- Use a min-heap to keep track of the K largest elements.
- Iterate through the array.
- Add the current element to the heap.
- If the heap size exceeds K, remove the smallest element.
- The root of the heap is the Kth largest element.
- C++
- Java
- Python
#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]