algoadvance

Leetcode 905. Sort Array By Parity

Problem Statement

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers. Return any array that satisfies this condition.

Example:

• Input: nums = [3, 1, 2, 4]
• Output: [2, 4, 3, 1]
  • The outputs [4, 2, 3, 1], [2, 4, 1, 3], and [4, 2, 1, 3] would also be accepted.

Clarifying Questions

1. Should the relative order of even and odd integers be maintained within their groups?
   • No, the relative order does not need to be maintained.
2. Can the input array contain negative integers?
   • Typically, the emphasis will be on even and odd regardless of negative signs, but let’s assume input as non-negative unless specified otherwise.
3. Is the input array mutable, i.e., can we modify it in place?
   • You can return a new array or modify it in place, as either approach results in valid output.

Let’s proceed with writing the solution in Java.

Strategy

We can use a two-pointer technique to rearrange the array in-place. The basic idea is to have one pointer start from the beginning (left = 0) and one from the end (right = nums.length - 1). We then swap elements if required as we traverse the array.

• Initialize two pointers: left at the beginning (0) and right at the end (nums.length - 1).
• Increment the left pointer until we find an odd number.
• Decrement the right pointer until we find an even number.
• Swap the elements at left and right pointers.
• Continue this process until the left pointer is greater than or equal to the right pointer.

By the end, all even numbers will be at the beginning of the array and all odd numbers at the end.

Code

public class SortArrayByParity {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            if (nums[left] % 2 != 0 && nums[right] % 2 == 0) {
                // Swap elements at left and right
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }

            if (nums[left] % 2 == 0) {
                left++;
            }
            if (nums[right] % 2 != 0) {
                right--;
            }
        }

        return nums;
    }

    public static void main(String[] args) {
        SortArrayByParity solution = new SortArrayByParity();
        int[] input = {3, 1, 2, 4};
        int[] result = solution.sortArrayByParity(input);
        // Print the result array
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

Time Complexity

• The time complexity of this approach is O(n), where n is the length of the array. We traverse the array from both ends towards the center, essentially touching each element once.
• The space complexity is O(1) since we are only using a couple of extra variables (left and right). We are modifying the array in place and not using extra space proportional to the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?