Group even and odd numbers.

Interviewers like this because it checks whether you can partition data cleanly instead of overcomplicating a tiny problem.

Question: Group even and odd numbers.

Answer: Put all even numbers together and all odd numbers together, usually in one array or list. The simplest fast solution is a two-pointer partition: scan from both ends, swap a wrong odd on the left with a wrong even on the right, and keep going until the pointers meet. This gives O(n) time and O(1) extra space. If the order inside each group matters, use extra storage for a stable version.

Interview-Ready Answer: I’d solve this with a two-pointer partition. I keep one pointer at the left and one at the right; when the left side stops on an odd number and the right side stops on an even number, I swap them. That groups all evens on one side and odds on the other in linear time, O(n), with constant extra space. If the interviewer asks to preserve the original order, I’d switch to a stable version using an extra list.

What the problem really asks

In interview language, group usually means partition: split values into two buckets, evens and odds. Unlike sorting, you do not need 2 before 4 before 6; you only need each number on the correct side.

How the in-place two-pointer solution works

1. Start a left pointer at index 0 and a right pointer at the last index.
2. Move the left pointer forward while it already points to an even number.
3. Move the right pointer backward while it already points to an odd number.
4. If the left pointer finds an odd number and the right pointer finds an even number, swap them.
5. Repeat until the pointers cross. At that point, everything on the left side is even and everything on the right side is odd.

This works because every swap fixes two mistakes at once: an odd number that was sitting too far left and an even number that was sitting too far right.

Why parity checks are simple in Java

Parity means whether a number is even or odd. In Java, n % 2 == 0 means even, and n % 2 != 0 means odd. A common alternative is (n & 1) == 0; the bitwise & operator looks at the last binary bit, which is 0 for even and 1 for odd. Both work for negative numbers too, but % 2 != 0 is easier for beginners to read.

When to use this approach

• Use in-place partitioning when memory matters and the order inside each group does not matter.
• Use a stable approach when the original order must stay the same, such as preserving event order in logs.
• Use the two-pointer version when the array is large and you want the simplest linear-time solution.

Comparison with a stable version

Performance and edge cases

The time complexity is O(n) because each pointer only moves forward or backward, and each element is examined a small number of times. In practice, if you had 1,000,000 integers, the algorithm still stays linear; it just does one pass over the data instead of repeatedly re-scanning it like a nested-loop solution would.

• Empty array: do nothing.
• Single element: already grouped.
• All evens or all odds: the loops just slide past them.
• Zero: it is even.
• Negative numbers: parity still works normally; odd negatives are still odd.

Memory model: the algorithm stores only a few indexes and one temporary variable for swapping, so the extra space is constant.

Real-World Story: Imagine a checkout service that batches order IDs before sending them to two worker pools, one for even IDs and one for odd IDs, so the system can split load evenly. The grouping step is tiny, but it protects the next stage from doing unnecessary checks and keeps the pipeline predictable.

What goes wrong if a developer assumes the grouping is stable when it is not? The same IDs still appear, but their order changes after swapping, so a reconciliation job comparing the grouped output against an ordered audit feed starts reporting mismatches. Symptoms include confusing log lines like sequence mismatch or unexpected order, operators chasing a phantom data corruption bug, and reports that look wrong even though the raw numbers are correct.

Follow-up Questions

• How would you preserve the original order? Use two temporary lists, one for evens and one for odds, then copy evens followed by odds back into the array. That is stable, but it costs O(n) extra space.
• Can this be done in one pass? Yes. The two-pointer method is already effectively one pass over the array because each pointer only moves inward and each misplaced pair is fixed immediately.
• What changes if the input is a linked list? You can relink nodes instead of swapping array values, often by building two sublists and stitching them together. That keeps the same parity idea but uses pointer manipulation instead of index access.
• Why might you use & 1 instead of % 2? Both are correct for parity, but & 1 is a fast bitwise check that directly reads the last binary digit. In interviews, readability usually matters more, so % 2 is perfectly fine.
• What if the interviewer says odd numbers should come first? Just flip the checks: move the left pointer until it finds an odd number and the right pointer until it finds an even number, then swap.

Tricky / Gotcha Questions

• Is n % 2 == 1 a correct odd test in Java? No. For negative odd numbers, Java gives a negative remainder, so -3 % 2 is -1, not 1. Use n % 2 != 0 or (n & 1) != 0 instead.
• Does grouping the numbers mean sorting them? No. Grouping only separates the two categories; it does not order the values within each category.
• Does the in-place method preserve relative order? No. Swaps can move earlier even numbers behind later even numbers, so it is not stable.

Common Mistakes:

• Using % 2 == 1 for odd numbers. Correction: use % 2 != 0 or & 1 so negative odd numbers are handled correctly.
• Thinking this is a sorting problem. Correction: only parity matters; the actual numeric order does not.
• Forgetting that zero is even. Correction: treat 0 as part of the even group.
• Assuming the two-pointer solution is stable. Correction: it is fast and space-efficient, but it may reorder numbers inside each group.

Memory Hook: Think of two bouncers in a hallway: the left bouncer pushes evens to the left door, the right bouncer pushes odds to the right door, and any misplaced guest gets swapped out immediately.

Cheat Sheet:

• Group usually means partition, not sort.
• Use two pointers: left finds odd, right finds even, then swap.
• Time: O(n). Extra space: O(1).
• Stable version: use extra lists, then concatenate.
• Zero is even; negative odd numbers are still odd.

Practice Tasks:

• Rewrite the solution so odd numbers come first instead of even numbers.
• Implement a stable version that preserves the order of evens and odds.
• Adapt the idea for a linked list instead of an array.