Sorting Problems

Posted on: February 1, 2025 Posted by: rahulgite Comments: 0

Problem 1: Sort Array By Parity

Explanation:

Given an integer array nums, we need to rearrange the elements so that all even numbers appear before all odd numbers. The order among even or odd numbers does not matter.

Approach:

  1. Two-Pointer Technique: We maintain two pointers: one at the beginning (left) and one at the end (right).
  2. Swap Strategy: If nums[left] is even, we move left forward. If nums[right] is odd, we move right backward. When we find an odd number at left and an even number at right, we swap them.
  3. Stop Condition: The process stops when left and right pointers meet.

Time & Space Complexity:

  • Time Complexity: O(n), since we traverse the array at most once.
  • Space Complexity: O(1), as we modify the array in-place.

Java Implementation:

public class SortArrayByParity {
    /**
     * Rearranges array such that even numbers appear before odd numbers.
     * @param nums input array
     * @return rearranged array
     * 
     * Time Complexity: O(n) - We traverse the array at most once.
     * Space Complexity: O(1) - In-place modifications, no extra space used.
     */
    public static int[] sortArrayByParity(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            // Swap if left is odd and right is even
            if (nums[left] % 2 > nums[right] % 2) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
            // Move left pointer forward if it's even
            if (nums[left] % 2 == 0) left++;
            // Move right pointer backward if it's odd
            if (nums[right] % 2 == 1) right--;
        }
        return nums;
    }
    
    public static void main(String[] args) {
        int[] input = {3, 1, 2, 4};
        int[] output = sortArrayByParity(input);
        System.out.print("Output: ");
        for (int num : output) {
            System.out.print(num + " ");
        }
    }
}

Example:

Input:

[3, 1, 2, 4]

Output:

[2, 4, 3, 1]

(or any other valid order where even numbers come first)

Edge Cases Considered:

  • All even numbers → No swaps needed.
  • All odd numbers → No swaps needed.
  • Alternating even and odd numbers → The algorithm correctly segregates them.
  • Empty array → Should return an empty array.

Problem 2: Squares of a Sorted Array

Explanation:

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Approach:

  1. Two-Pointer Technique: Since negative numbers square to positive values, the largest squared value may come from either end of the array.
  2. Comparison Strategy: Start two pointers at the left (0) and right (n - 1) positions and move towards the center.
  3. Insert in Reverse Order: Store the maximum squared value at the end of the result array and move the respective pointer.

Time & Space Complexity:

  • Time Complexity: O(n), since we process each element once.
  • Space Complexity: O(n), as we use an additional array to store results.

Java Implementation:

public class SquaresOfSortedArray {
    /**
     * Returns an array of squares sorted in non-decreasing order.
     * @param nums input sorted array
     * @return squared and sorted array
     * 
     * Time Complexity: O(n) - Each element is processed once.
     * Space Complexity: O(n) - Additional array is used for results.
     */
    public static int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 0, right = n - 1;
        int index = n - 1;
        
        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            if (leftSquare > rightSquare) {
                result[index--] = leftSquare;
                left++;
            } else {
                result[index--] = rightSquare;
                right--;
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] input = {-4, -1, 0, 3, 10};
        int[] output = sortedSquares(input);
        System.out.print("Output: ");
        for (int num : output) {
            System.out.print(num + " ");
        }
    }
}

Example:

Input:

[-4, -1, 0, 3, 10]

Output:

[0, 1, 9, 16, 100]

Edge Cases Considered:

  • All positive numbers → Normal case, already sorted.
  • All negative numbers → Reversed order, but squares will be sorted.
  • Mix of positives and negatives → Handles using the two-pointer approach.
  • Single element → Should return its square.
  • Empty array → Should return an empty array.

Problem 3: Sort Colors

Explanation:

Given an array nums containing n objects colored red (0), white (1), or blue (2), sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

Approach:

  1. Dutch National Flag Algorithm: Use three pointers: low, mid, and high.
  2. Swap Strategy:
    • If nums[mid] == 0, swap nums[mid] with nums[low] and move both pointers forward.
    • If nums[mid] == 1, move mid forward.
    • If nums[mid] == 2, swap nums[mid] with nums[high] and move high backward.
  3. Stop Condition: The loop runs while mid is less than or equal to high.

Time & Space Complexity:

  • Time Complexity: O(n), since we traverse the array at most once.
  • Space Complexity: O(1), as we modify the array in-place.

Java Implementation:

public class SortColors {
    /**
     * Sorts an array containing 0s, 1s, and 2s in-place.
     * @param nums input array
     * 
     * Time Complexity: O(n) - Each element is processed at most once.
     * Space Complexity: O(1) - In-place sorting.
     */
    public static void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;
        
        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low++, mid++);
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums, mid, high--);
            }
        }
    }
    
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    public static void main(String[] args) {
        int[] input = {2, 0, 2, 1, 1, 0};
        sortColors(input);
        System.out.print("Output: ");
        for (int num : input) {
            System.out.print(num + " ");
        }
    }
}

Example:

Input:

[2, 0, 2, 1, 1, 0]

Output:

[0, 0, 1, 1, 2, 2]

Edge Cases Considered:

  • Already sorted array → Algorithm should maintain order.
  • Reverse sorted array → Algorithm should correctly reorder.
  • All identical numbers → No changes needed.
  • Single element array → Should remain the same.
  • Empty array → Should remain unchanged.

Problem 4: Top K Frequent Elements

Explanation:

Given an integer array nums and an integer k, return the k most frequent elements. The answer should be in any order.

Approach:

  1. HashMap for Frequency Count: Traverse the array and store the frequency of each element in a hashmap.
  2. Bucket Sort Approach:
    • Create an array of lists where the index represents the frequency of numbers.
    • Place each number in the corresponding frequency bucket.
  3. Extract Top K Elements: Traverse from the highest frequency downwards and collect elements until k elements are gathered.

Time & Space Complexity:

  • Time Complexity: O(n), since we iterate through the array and then collect elements from the buckets.
  • Space Complexity: O(n), as we use extra storage for buckets.

Java Implementation:

import java.util.*;

public class TopKFrequentElements {
    /**
     * Returns the k most frequent elements in an array using bucket sort.
     * @param nums input array
     * @param k number of top frequent elements to return
     * @return array of k most frequent elements
     * 
     * Time Complexity: O(n) - Building frequency map and processing buckets.
     * Space Complexity: O(n) - Extra storage for buckets.
     */
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        List<Integer>[] buckets = new List[nums.length + 1];
        for (int key : frequencyMap.keySet()) {
            int freq = frequencyMap.get(key);
            if (buckets[freq] == null) {
                buckets[freq] = new ArrayList<>();
            }
            buckets[freq].add(key);
        }
        
        List<Integer> resultList = new ArrayList<>();
        for (int i = buckets.length - 1; i >= 0 && resultList.size() < k; i--) {
            if (buckets[i] != null) {
                resultList.addAll(buckets[i]);
            }
        }
        
        return resultList.stream().mapToInt(i -> i).toArray();
    }
    
    public static void main(String[] args) {
        int[] input = {1, 1, 1, 2, 2, 3};
        int k = 2;
        int[] output = topKFrequent(input, k);
        System.out.print("Output: ");
        for (int num : output) {
            System.out.print(num + " ");
        }
    }
}

Example:

Input:

nums = [1,1,1,2,2,3], k = 2

Output:

[1, 2]

Edge Cases Considered:

  • All unique elements → Each element appears once, return k largest elements.
  • All elements same → Only one unique element but requested k most frequent.
  • k equals array size → Return all elements sorted by frequency.
  • Empty array → Should return an empty array.

Problem 5: Top K Frequent Words

Explanation:

Given an array of strings words and an integer k, return the k most frequent words. The answer should be sorted by frequency from highest to lowest. If two words have the same frequency, sort them lexicographically.

Approach:

  1. HashMap for Frequency Count: Traverse the list and store the frequency of each word in a hashmap.
  2. Min-Heap (Priority Queue): Maintain a min-heap of size k that orders words based on:
    • Higher frequency comes first.
    • If frequencies are equal, words are sorted lexicographically.
  3. Extract and Reverse: Pop elements from the heap to construct the final result in order.

Time & Space Complexity:

  • Time Complexity: O(n log k), since we insert into the heap n times with log k complexity.
  • Space Complexity: O(n), used for hashmap and heap.

Java Implementation:

import java.util.*;

public class TopKFrequentWords {
    /**
     * Returns the k most frequent words in an array.
     * @param words input list of words
     * @param k number of top frequent words to return
     * @return list of k most frequent words
     * 
     * Time Complexity: O(n log k) - Heap insertion/removal takes log k time.
     * Space Complexity: O(n) - HashMap and Heap usage.
     */
    public static List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> frequencyMap = new HashMap<>();
        for (String word : words) {
            frequencyMap.put(word, frequencyMap.getOrDefault(word, 0) + 1);
        }
        
        PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> 
            frequencyMap.get(a).equals(frequencyMap.get(b)) ? a.compareTo(b) : frequencyMap.get(b) - frequencyMap.get(a));
        
        heap.addAll(frequencyMap.keySet());
        
        List<String> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(heap.poll());
        }
        return result;
    }
    
    public static void main(String[] args) {
        String[] input = {"i", "love", "leetcode", "i", "love", "coding"};
        int k = 2;
        List<String> output = topKFrequent(input, k);
        System.out.println("Output: " + output);
    }
}

Example:

Input:

words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2

Output:

["i", "love"]

Edge Cases Considered:

  • Words with the same frequency → Sorted lexicographically.
  • All words are unique → Return k words in sorted order.
  • k equals number of unique words → Return all words sorted by frequency.
  • Empty list → Should return an empty list.

Problem 6: Sort Characters By Frequency

Explanation:

Given a string s, sort it in decreasing order based on the frequency of characters.

Approach:

  1. HashMap for Frequency Count: Traverse the string and store the frequency of each character in a hashmap.
  2. Bucket Sort Approach:
    • Create an array of lists where the index represents the frequency of characters.
    • Place each character in the corresponding frequency bucket.
  3. Build the Result String: Traverse from the highest frequency downwards and construct the result string.

Time & Space Complexity:

  • Time Complexity: O(n), since we iterate through the string and then collect elements from the buckets.
  • Space Complexity: O(n), as we use extra storage for buckets.

Java Implementation:

import java.util.*;

public class SortCharactersByFrequency {
    /**
     * Returns a string sorted in decreasing order of character frequency.
     * @param s input string
     * @return sorted string by frequency
     * 
     * Time Complexity: O(n) - Building frequency map and processing buckets.
     * Space Complexity: O(n) - Extra storage for buckets.
     */
    public static String frequencySort(String s) {
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }
        
        List<Character>[] buckets = new List[s.length() + 1];
        for (char key : frequencyMap.keySet()) {
            int freq = frequencyMap.get(key);
            if (buckets[freq] == null) {
                buckets[freq] = new ArrayList<>();
            }
            buckets[freq].add(key);
        }
        
        StringBuilder result = new StringBuilder();
        for (int i = buckets.length - 1; i >= 0; i--) {
            if (buckets[i] != null) {
                for (char c : buckets[i]) {
                    result.append(String.valueOf(c).repeat(i));
                }
            }
        }
        
        return result.toString();
    }
    
    public static void main(String[] args) {
        String input = "tree";
        String output = frequencySort(input);
        System.out.println("Output: " + output);
    }
}

Example:

Input:

s = "tree"

Output:

"eert"

(or “eetr”, as order does not matter when frequencies are the same)

Edge Cases Considered:

  • All unique characters → Original order remains.
  • All characters the same → Output is the same as input.
  • Mix of different frequencies → Sorted correctly.
  • Empty string → Should return an empty string.

Problem 7: Merge Intervals

Explanation:

Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return an array of non-overlapping intervals that cover all the intervals in the input.

Approach:

  1. Sort Intervals: First, sort the intervals based on their start times.
  2. Merge Overlapping Intervals:
    • Initialize a list to store merged intervals.
    • Iterate through the sorted intervals, merging overlapping ones by updating the end time.
  3. Store Merged Intervals: Add the non-overlapping intervals to the result list.

Time & Space Complexity:

  • Time Complexity: O(n log n), due to sorting the intervals.
  • Space Complexity: O(n), for storing the result.

Java Implementation:

import java.util.*;

public class MergeIntervals {
    /**
     * Merges overlapping intervals.
     * @param intervals input array of intervals
     * @return merged intervals
     * 
     * Time Complexity: O(n log n) - Sorting takes O(n log n), merging takes O(n).
     * Space Complexity: O(n) - Storing merged intervals.
     */
    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][0];
        
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> merged = new ArrayList<>();
        
        for (int[] interval : intervals) {
            if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
            }
        }
        
        return merged.toArray(new int[merged.size()][]);
    }
    
    public static void main(String[] args) {
        int[][] input = {{1,3}, {2,6}, {8,10}, {15,18}};
        int[][] output = merge(input);
        System.out.print("Output: ");
        for (int[] interval : output) {
            System.out.print("[" + interval[0] + "," + interval[1] + "] ");
        }
    }
}

Example:

Input:

intervals = [[1,3],[2,6],[8,10],[15,18]]

Output:

[[1,6],[8,10],[15,18]]

Edge Cases Considered:

  • No overlapping intervals → Output remains the same as input.
  • All intervals overlap → Merges into one interval.
  • Intervals are already merged → No changes needed.
  • Single interval → Should return the same interval.
  • Empty input → Should return an empty list.

Problem 8: Unique Number of Occurrences

Explanation:

Given an array of integers arr, return true if the number of occurrences of each value in the array is unique, or false otherwise.

Approach:

  1. HashMap for Frequency Count: Traverse the array and store the frequency of each number.
  2. Set to Check Uniqueness: Store the frequencies in a HashSet to check for duplicates.
  3. Return Result: If all frequencies are unique, return true; otherwise, return false.

Time & Space Complexity:

  • Time Complexity: O(n), since we traverse the array and process elements in the HashMap and HashSet.
  • Space Complexity: O(n), used for storing frequencies.

Java Implementation:

import java.util.*;

public class UniqueOccurrences {
    /**
     * Checks if the occurrences of each value in the array are unique.
     * @param arr input array
     * @return true if occurrences are unique, false otherwise
     * 
     * Time Complexity: O(n) - Single pass through the array and processing.
     * Space Complexity: O(n) - HashMap and HashSet usage.
     */
    public static boolean uniqueOccurrences(int[] arr) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        Set<Integer> occurrenceSet = new HashSet<>(frequencyMap.values());
        return occurrenceSet.size() == frequencyMap.size();
    }
    
    public static void main(String[] args) {
        int[] input = {1, 2, 2, 1, 1, 3};
        boolean output = uniqueOccurrences(input);
        System.out.println("Output: " + output);
    }
}

Example:

Input:

arr = [1,2,2,1,1,3]

Output:

true

Edge Cases Considered:

  • All elements occur once → Should return true.
  • Multiple elements with the same frequency → Should return false.
  • Single element array → Should return true.
  • Empty array → Should return true.

Problem 9: Find Peak Element

Explanation:

Given an integer array nums, find a peak element. A peak element is an element that is strictly greater than its neighbors.

Approach:

  1. Binary Search:
    • Compare the middle element with its neighbors.
    • If nums[mid] is greater than nums[mid+1], the peak lies in the left half.
    • Otherwise, the peak lies in the right half.
    • Recursively continue until the peak is found.

Time & Space Complexity:

  • Time Complexity: O(log n), since we use binary search.
  • Space Complexity: O(1), as we use only constant extra space.

Java Implementation:

public class PeakElement {
    /**
     * Finds a peak element in an array.
     * @param nums - input array
     * @return index of any peak element
     */
    public static int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        System.out.println("Output: " + findPeakElement(nums));
    }
}

Example:

Input:

nums = [1,2,3,1]

Output:

2

Edge Cases Considered:

  • Single-element array → Should return index 0.
  • Multiple peaks → Any peak is valid.
  • Strictly increasing or decreasing array → Should return last or first index.

Problem 10: H-Index

Explanation:

Given an array citations where citations[i] is the number of citations a researcher received for their i-th paper, return the researcher’s H-Index.

Approach:

  1. Counting Sort:
    • Create an array count of size n + 1 where count[i] stores the number of papers with i citations.
    • Compute cumulative sum from the back to find the highest h where count[h] >= h.

Time & Space Complexity:

  • Time Complexity: O(n), since we only iterate through the list twice.
  • Space Complexity: O(n), for storing frequency counts.

Java Implementation:

public class HIndex {
    /**
     * Computes the researcher's H-Index.
     * @param citations - array of citation counts
     * @return H-Index value
     */
    public static int hIndex(int[] citations) {
        int n = citations.length;
        int[] count = new int[n + 1];
        
        for (int c : citations) {
            count[Math.min(c, n)]++;
        }
        
        int h = 0;
        for (int i = n; i >= 0; i--) {
            h += count[i];
            if (h >= i) return i;
        }
        return 0;
    }
    
    public static void main(String[] args) {
        int[] citations = {3, 0, 6, 1, 5};
        System.out.println("Output: " + hIndex(citations));
    }
}

Example:

Input:

citations = [3, 0, 6, 1, 5]

Output:

3

Edge Cases Considered:

  • All citations are zero → Should return 0.
  • Already sorted citations → Should still work correctly.
  • Large citation counts → Should correctly cap at n.

Leave a Comment