Array DSA Problems

Array DSA Problems | Also see:- Arrays, Bit Manipulation and Math DSA Problems

Table of Contents

• Majority Element II
• Next Permutation
• Matrix
  • Set Matrix Zeroes
  • Diagonal Traverse of Matrix
• Plus One
• Roman to Integer
• Frequency of the Most Frequent Element
• Check if the Array Is Sorted and Rotated
• Maximum Score from Subarray Minimums
• Pascal’s Triangle
  • 1. Given R and C, find the element in row R and Column C
  • 2. Print the nth row of the Pascal Triangle
  • 3. Print a complete Pascal Triangle for N = 6
• 3Sum
• 4Sum
• Hashing & PriorityQueue
  • Top K Frequent Elements
• String
  • First Unique Character in a String

Majority Element II

This problem is an extension of the Boyer-Moore Voting Algorithm. You are given an array of integer arr[ ] where each number represents a vote to a candidate. Return the candidates that have votes greater than one-third of the total votes, If there’s not a majority vote, return an empty array. Note: The answer should be returned in an increasing format. Problem Link.

Input: arr[] = [2, 1, 5, 5, 5, 5, 6, 6, 6, 6, 6]
Output: [5, 6]
Explanation: 5 and 6 occur more n/3 times.

Input: arr[] = [1, 2, 3, 4, 5]
Output: []
Explanation: no candidate occur more than n/3 times.

import java.util.ArrayList;
import java.util.List;

public class Test {

    public static void main(String[] args) {
        int arr[] = { 2, 1, 5, 5, 5, 5, 6, 6, 6, 6, 6 };
        System.out.println(findMajority(arr));
    }

    public static List<Integer> findMajority(int[] nums) {
        int ele1 = -1, ele2 = -1, count1 = 0, count2 = 0, n = nums.length;
        for (int k : nums) {
            if (k == ele1) {
                count1++;
            } else if (k == ele2) {
                count2++;
            } else if (count1 == 0) {
                ele1 = k;
                count1++;
            } else if (count2 == 0) {
                ele2 = k;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        // validate
        count1 = count2 = 0;
        for (int k : nums) {
            if (k == ele1) {
                count1++;
            } else if (k == ele2) {
                count2++;
            }
        }
        // Add to result if they are majority elements
        List<Integer> result = new ArrayList<>();
        if (count1 > n / 3) {
            result.add(ele1);
        }
        if (count2 > n / 3) {
            result.add(ele2);
        }
        if (result.size() == 2 && result.get(1) < result.get(0)) {
            int temp = result.get(0);
            result.set(0, result.get(1));
            result.set(1, temp);
        }
        return result;
    }
}

Next Permutation

Given an array of integers arr[] representing a permutation, implement the next permutation that rearranges the numbers into the lexicographically next greater permutation. If no such permutation exists, rearrange the numbers into the lowest possible order (i.e., sorted in ascending order). Problem: 31. Solution

Note – A permutation of an array of integers refers to a specific arrangement of its elements in a sequence or linear order.

Input: arr = [2, 4, 1, 7, 5, 0]
Output: [2, 4, 5, 0, 1, 7]
Explanation: The next permutation of the given array is {2, 4, 5, 0, 1, 7}.

Input: arr = [3, 2, 1]
Output: [1, 2, 3]
Explanation: As arr[] is the last permutation, the next permutation is the lowest one.

Step:-

• Identify the rightmost element which is smaller than its next element. Consider this element as a pivot element.
• Find the rightmost element greater than the pivot element.
• Swap pivot and rightmost greater element.
• Reverse the elements to the right of the pivot.

import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        int arr[] = { 2, 4, 1, 7, 5, 0 };
        nextPermutation(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void nextPermutation(int[] arr) {
        int pivot = -1, n = arr.length;

        // find pivot index
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] < arr[i + 1]) {
                pivot = i;
                break;
            }
        }
        // if pivot point does not exist then reverse
        if (pivot == -1) {
            reverse(arr, 0, n - 1);
            return;
        }
        // Find the element from the right that is greater than pivot
        for (int i = n - 1; i > pivot; i--) {
            if (arr[i] > arr[pivot]) {
                swap(arr, i, pivot);
                break;
            }
        }

        // reverse the elements from pivot+1 to end
        reverse(arr, pivot + 1, n - 1);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    private static void reverse(int[] arr, int i, int j) {
        while (i < j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
}

Matrix

Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s. You must do it in place. Problem: 73. Solution.

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Steps:

1. Initialize Variables:

• col0 to track if the first column should be set to zero.
• rows and cols to store the dimensions of the matrix.

2. First Pass: Traverse the matrix and use the first row and column to mark which rows and columns should be zeroed.
3. Second Pass: Traverse the matrix again in reverse order to set the elements to zero based on the markers in the first row and column.

class Solution {
    public void setZeroes(int[][] matrix) {
        // Initialize variables
        int col0 = 1; // To track if the first column needs to be zero
        int rows = matrix.length;
        int cols = matrix[0].length;

        // First pass: use the first row and column to mark zero rows and columns
        for (int i = 0; i < rows; i++) {
            if (matrix[i][0] == 0) {
                col0 = 0; // Mark first column to be zeroed
            }
            for (int j = 1; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0; // Mark row to be zeroed
                    matrix[0][j] = 0; // Mark column to be zeroed
                }
            }
        }

        // Second pass: set matrix elements to zero based on the markers
        // traverse in reverse from bottom-right
        for (int i = rows - 1; i >= 0; i--) {
            for (int j = cols - 1; j > 0; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0; // Set element to zero
                }
            }
            if (col0 == 0) {
                matrix[i][0] = 0; // Zero the first column if needed
            }
        }
    }
}

Explanation:

1. Initialization: col0 is used to track if the first column needs to be set to zero. rows and cols store the dimensions of the matrix.
2. First Pass:

• Loop through each row.
• If an element in the first column is zero, set col0 to zero.
• For other columns, if an element is zero, mark the corresponding first row and first column elements as zero.

3. Second Pass:

• Loop through the matrix in reverse order.
• Set elements to zero based on the markers in the first row and column.
• Zero the first column if col0 is set to zero.

Diagonal Traverse of Matrix

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order. Problem: 498. Solution.

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        if(mat.length ==0|| mat[0].length==0){
            return new int[]{};
        }
        int m=mat.length, n=mat[0].length;
        int[] res = new int[m*n];
        int row = 0, col=0;
        for(int i=0; i<m*n; i++){
            res[i] = mat[row][col];
            if((row + col)%2 == 0){
                // even; upwards
                if(col == n-1){
                    row++;
                } else if(row == 0){
                    col++;
                } else {
                    row--;
                    col++;
                }
            } else {
                // odd; downwards
                if(row == m-1){
                    col++;
                } else if(col == 0){
                    row++;
                } else {
                    row++;
                    col--;
                }
            }
        }
        return res;
    }
}

Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0’s. Increment the large integer by one and return the resulting array of digits. Problem Link: 66

Digits = [1,2,3], Output: [1,2,4]
Digits = [4,3,2,1], Output: [4,3,2,2]
Digits = [9], Output: [1,0]

import java.util.Arrays;

public class Test {
    public static int[] plusOne(int[] digits) {
        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            digits[i] = 0;
        }
        // If all the digits are 9
        int[] newNumber = new int[n + 1];
        newNumber[0] = 1;
        return newNumber;
    }

    public static void main(String[] args) {
        int[] digits1 = { 1, 2, 3 };
        int[] digits2 = { 4, 3, 2, 1 };
        int[] digits3 = { 9 };

        System.out.println(Arrays.toString(plusOne(digits1))); // Output: [1, 2, 4]
        System.out.println(Arrays.toString(plusOne(digits2))); // Output: [4, 3, 2, 2]
        System.out.println(Arrays.toString(plusOne(digits3))); // Output: [1, 0]
    }
}

Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol	Value
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a Roman numeral, convert it to an integer. Problem Link:- 13. Solution

import java.util.HashMap;
import java.util.Map;

public class RomanToInteger {
    public static void main(String[] args) {
        System.out.println(romanToInt("III"));    // Output: 3
        System.out.println(romanToInt("IV"));     // Output: 4
        System.out.println(romanToInt("IX"));     // Output: 9
        System.out.println(romanToInt("LVIII"));  // Output: 58
        System.out.println(romanToInt("MCMXCIV"));// Output: 1994
    }

    private static int romanToInt(String string) {
        Map<Character, Integer> romanMap = new HashMap<>();
        romanMap.put('I', 1);
        romanMap.put('V', 5);
        romanMap.put('X', 10);
        romanMap.put('L', 50);
        romanMap.put('C', 100);
        romanMap.put('D', 500);
        romanMap.put('M', 1000);

        int result = romanMap.get(string.charAt(string.length() - 1));
        for (int i = string.length() - 2; i >= 0; i--) {
            if (romanMap.get(string.charAt(i)) < romanMap.get(string.charAt(i + 1))) {
                result -= romanMap.get(string.charAt(i));
            } else {
                result += romanMap.get(string.charAt(i));
            }
        }
        return result;
    }
}

Frequency of the Most Frequent Element

The frequency of an element is the number of times it occurs in an array. You are given an integer array of nums and an integer k. In one operation, you can choose an index of nums and increment the element at that index by 1. Return the maximum possible frequency of an element after performing at most k operations. Problem: 1838. Solution.

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length, l = 0, r = 0, ans = 0;
        long sum = nums[0]; // use long
        while (r < n) {
            if (nums[r] * (long) (r - l + 1) <= sum + k) { // use long
                ans = Math.max(ans, r - l + 1);
                r++;
                if (r < n) {
                    sum += nums[r];
                }
            } else {
                sum -= nums[l];
                l++;
            }
        }
        return ans;
    }
}

Check if the Array Is Sorted and Rotated

Input: [3,4,5,1,2], Output: true, Explanation: [1,2,3,4,5] is the original sorted array. You can rotate the array by x = 3 positions to begin on the element of value 3: [3,4,5,1,2]. Problem: 1752. Solution

There may be duplicates in the original array.

class Solution {
    public boolean check(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > nums[(i + 1) % nums.length]) {
                count++;
            }
            if (count > 1) {
                return false;
            }
        }
        return true;
    }
}

Maximum Score from Subarray Minimums

Given an array arr[ ], with 0-based indexing, select any two indexes, i and j such that i < j. From the subarray arr[i…j], select the smallest and second smallest numbers and add them, you will get the score for that subarray. Return the maximum possible score across all the subarrays of array arr[ ]. Problem. Solution.

arr[] = [4, 3, 1, 5, 6]
11

class Solution {
    public int pairWithMaxSum(int arr[]) {
        int max = arr[0] + arr[1];
        for(int i=1; i<arr.length -1; i++){
            max = Math.max(max, arr[i] + arr[i+1]);
        }
        return max;
    }
}

Pascal’s Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle. Problem. Solution. In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:-

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Questions on Pascal Triangle:-

1. Given R and C, find the element in row R and Column C.
2. Print the nth row of the Pascal triangle.
3. Print complete Pascal triangle for N=6.

1. Given R and C, find the element in row R and Column C

The formula for this: ^{r-1C_c-1 nC_r = n! / (r! * (n-r)!)
4C₂ = 4! / (2! * (4-2)!) = 4! / (2 * 2) = 6}

There is a shortcut to calculate ⁿC_r.
¹⁰C₃ = (10 * 9 * 8) / (3 * 2 * 1) = 10/1 + 9/2 + 8/3

public class Test {
    public static void main(String[] args) {
        int n = 10, r = 3;
        System.out.println(ncr(n, r));
    }

    private static long ncr(int n, int r) {
        long res = 1; // use long
        for (int i = 0; i < r; i++) {
            res *= (n - i);
            res /= (i + 1);
        }
        return res;
    }
}

Time complexity: O(r)

2. Print the nth row of the Pascal Triangle

The nth row will have n elements from ⁿC₁ to ⁿC_n. It can be found as:-

for c = 1 to n:
   print(ncr(n, c))

But it will have a time complexity of O(n *r). To optimize:-

public class Test {
    public static void main(String[] args) {
        int n = 5;
        printNthRowOfPascal(n); // 1 4 6 4 1 
    }

    private static void printNthRowOfPascal(int n) {
        int ans = 1;
        System.out.print(ans + " ");
        for (int col = 1; col < n; col++) {
            ans *= (n - col);
            ans /= col;
            System.out.print(ans + " ");
        }
    }
}

But if we have to return the rowIndexth (0-indexed) row of the Pascal’s triangle as Problem: 119 then while calculating ans we can do:-

ans *= (n - col + 1);

3. Print a complete Pascal Triangle for N = 6

import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        int n = 5;
        System.out.println(pascalTraingle(n));
    }

    private static List<List<Integer>> pascalTraingle(int n) {
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            list.add(nthRowOfPascalTraingle(i));
        }
        return list;
    }

    private static List<Integer> nthRowOfPascalTraingle(int n) {
        List<Integer> list = new ArrayList<>();
        int ans = 1;
        list.add(ans);
        for (int col = 1; col < n; col++) {
            ans *= (n - col);
            ans /= col;
            list.add(ans);
        }
        return list;
    }
}

3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Problem: 15. Solution.

nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        int[] arr = { -1, 0, 1, 2, -1, -4 };
        System.out.println(threeSum(arr));
    }

    private static List<List<Integer>> threeSum(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> ans = new ArrayList<>();
        int n = arr.length;
        for (int i = 0; i < arr.length; i++) {
            if (i > 0 && arr[i] == arr[i - 1]) {
                continue;
            }
            // two pointers
            int j = i + 1; // pointer at start position
            int k = n - 1;// pointer at end position
            while (j < k) {
                int sum = arr[i] + arr[j] + arr[k];
                if (sum == 0) {
                    ans.add(List.of(arr[i], arr[j], arr[k]));
                    j++;
                    k--;
                    // skip duplicates
                    while (j < k && arr[j] == arr[j - 1]) {
                        j++;
                    }
                    while (j < k && arr[k] == arr[k + 1]) {
                        k--;
                    }
                } else if (sum > 0) {
                    k--;
                } else {
                    j++;
                }
            }
        }
        return ans;
    }
}

Time complexity: n * log(n) for sorting + O(n * n) for iteration => O(n^2). Auxiliary Space: O(1).

4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order. Problem: 18. Solution.

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        int[] arr = { 2, 2, 2, 2, 2 };
        int target = 8;
        System.out.println(fourSum(arr, target));
    }

    private static List<List<Integer>> fourSum(int[] arr, int target) {
        Arrays.sort(arr);
        List<List<Integer>> ans = new ArrayList<>();
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            if (i > 0 && arr[i] == arr[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n; j++) {
                // j does not skip when it is directly after i
                if (j > i + 1 && arr[j] == arr[j - 1]) {
                    continue;
                }
                // two pointers
                int k = j + 1; // pointer at start position
                int l = n - 1;// pointer at end position
                while (k < l) {
                    // use long
                    long sum = (long) arr[i] + arr[j] + arr[k] + arr[l];
                    if (sum == target) {
                        ans.add(List.of(arr[i], arr[j], arr[k], arr[l]));
                        k++;
                        l--;
                        // skip duplicates
                        while (k < l && arr[k] == arr[k - 1]) {
                            k++;
                        }
                        while (k < l && arr[l] == arr[l + 1]) {
                            l--;
                        }
                    } else if (sum > target) {
                        l--;
                    } else {
                        k++;
                    }
                }
            }
        }
        return ans;
    }
}

Hashing & PriorityQueue

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Problem: 347

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Input: nums = [1], k = 1
Output: [1]

This problem can be efficiently solved using a combination of a HashMap and a PriorityQueue. Approach:

1. Frequency Count: Use a HashMap to count the frequency of each element.
2. Min-Heap: Use a PriorityQueue (min-heap) to keep track of the top K elements based on their frequency.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        int[] nums = { 1, 1, 1, 2, 2, 3 };
        int k = 2;
        System.out.println(Arrays.toString(topKElements(nums, k))); // [2, 1]
    }

    private static int[] topKElements(int[] nums, int k) {
        // Step 1: Count the frequency of each element
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        // Step 2: Use a min-heap to keep the top k elements
        PriorityQueue<Entry<Integer, Integer>> minHeap = 
                new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        for (Entry<Integer, Integer> e : map.entrySet()) {
            minHeap.add(e);
            if (minHeap.size() > k) {
                minHeap.poll(); // remove element with least occurrence
            }
        }
        // Step 3: Extract the elements from the min-heap
        int[] result = new int[k];
        int i = 0;
        while (!minHeap.isEmpty()) {
            result[i++] = minHeap.poll().getKey();
        }
        return result;
    }
}

Explanation:

1. Frequency Map: The HashMap freqMap counts the occurrences of each element in the array.
2. Min-Heap Initialization: The PriorityQueue minHeap is used to maintain the top K elements by their frequency. The heap size is maintained at K by removing the smallest frequency element whenever the size exceeds K.
3. Result Extraction: The elements in the min-heap are the top K frequent elements, which are then extracted and added to the result list.

This implementation ensures that the solution runs efficiently, with a time complexity of O(N log K), where N is the number of elements in the array.

String

First Unique Character in a String

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1. Problem: 387

Input: s = “leetcode”
Output: 0

Explanation: The character ‘l’ at index 0 is the first character that does not occur at any other index.

Input: s = “aabb”
Output: -1

class Solution {
    public int firstUniqChar(String s) {
        int[] freq = new int[26];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (freq[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search