O(n), for the auxiliary array.

Method 2 - Naive - Shifting 1 by 1

Here is the approach:

Shifting Elements:
- One by one, shift elements from the second half of the array to their correct positions in the left half.
- Use two pointers to keep track of elements to be swapped.
In-place Swapping:
- Perform necessary swaps to achieve the desired rearrangement without using extra space.

Here is the visualization of how the logic will continue: rearrange-array-elements-first-and-second-half-in-alternating-order-viz-naive1.excalidraw

Code

[{"language":"Java","code":"public class Solution {\n    public void rearrangeArray(int[] nums) {\n        int n = nums.length / 2;  // Calculate n from array length\n        int start = 0;\n        int end = nums.length - 1;\n        int mid = start + (end - start) / 2;\n\n        while (start < n && mid < end) {\n            int leftIndex = start + 1;\n            int rightIndex = mid + 1;\n            while (leftIndex < rightIndex) {\n                swap(nums, rightIndex, rightIndex - 1);\n                rightIndex--;\n            }\n            start += 2;\n            mid += 1;\n        }\n\n        // Print the rearranged array\n        for (int i = 0; i < nums.length; i++) {\n            System.out.print(nums[i] + \" \");\n        }\n        System.out.println();\n    }\n\n    private void swap(int[] nums, int m, int n) {\n        int temp = nums[m];\n        nums[m] = nums[n];\n        nums[n] = temp;\n    }\n\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> void</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> rearrangeArray</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">[] </span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">nums</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> nums.length </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">/</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 2</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;  </span><span style=\"color:#6A737D;--shiki-dark:#6A737D\">// Calculate n from array length</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> start </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"><span style

Related Tags