Unequal Adjacent Elements in Java

An array containing n numbers of positive and negative numbers is given. The given problem involves rearranging the elements of an array in such a way that no two adjacent elements are equal. This means that if there are any repeated numbers in the array, they should not appear next to each other after the rearrangement. if the given input array does not contain any valid arrangement then it displays an appropriate message.

Example 1

Input:

arr[] = { 5, 5, 9, 7}

Output:

{5, 9, 5, 7}

Explanation: There are multiple possible arrangements. Those valid arrangements are given below. {5, 9, 5, 7}, {5, 9, 7, 5}, {7, 5, 9, 5}, {9, 5, 7, 5}, { 5, 7, 5, 9 }, { 5, 7, 9, 5}. From these valid arrangements first one is mentioned in the output which is {5, 9, 5, 7}.

Example 2

Input:

arr[] = { 3, 5, 9, 7, 8, 4}

Output:

{ 3, 5, 9, 7, 8, 4}

Explanation: In the given input array no equal elements are adjacent. So the output remains the same and the Input array is the answer.

Approach: Backtracking Algorithm

Here we are using a backtracking approach to solve the problem of rearranging elements in the array. It recursively generates all possible rearrangements by exploring different choices and backtracking when a valid arrangement cannot be found. The algorithm checks each element in the array and determines if it can be placed at the current index based on the previously rearranged elements. If a valid arrangement is found, it returns true; otherwise, it backtracks and explores other options.

FileName: UnequalAdjacentEle.java

import java.util.Arrays;
public class UnequalAdjacentEle {
 public static void main(String[] args) {
 int[] array = {2, 3, 3, 4, 5, 5, 6};
 int[] rearrangedArray = rearrangeArray(array);
 if (rearrangedArray != null) {
 System.out.println("Rearranged array: " + Arrays.toString(rearrangedArray)); // Print the rearranged array
 } else {
 System.out.println("No valid arrangement exists."); // If no valid arrangement exists, display a message
 }
 }
 public static int[] rearrangeArray(int[] array) {
 int n = array.length;
 boolean[] visited = new boolean[n]; // Keeps track of visited elements
 // Create a temporary array to store the rearranged elements
 int[] tempArray = new int[n];
 // Start rearranging from index 0
 if (rearrangeUtil(array, visited, tempArray, 0)) {
 return tempArray;
 }
 return null; // No valid arrangement exists
 }
 // Helper function that recursively generates all possible rearrangements
 private static boolean rearrangeUtil(int[] array, boolean[] visited, int[] tempArray, int index) {
 if (index == array.length) {
 return true; // Valid arrangement found
 }
 for (int i = 0; i < array.length; i++) {
 if (!visited[i] && (index == 0 || array[i] != tempArray[index - 1])) {
 visited[i] = true; // Mark element as visited
 tempArray[index] = array[i]; // Store element in temporary array
 if (rearrangeUtil(array, visited, tempArray, index + 1)) {
 return true; // Recurse to the next index
 }
 visited[i] = false; // Backtrack (unmark element)
 }
 }
 return false; // No valid arrangement found
 }
}

Output:

Rearranged array: [2, 3, 4, 3, 5, 6, 5]

Complexity:

the overall time complexity of the code can be approximated as O(n log n) + O(n!). In practice, the actual time complexity will depend on the specific input array and the number of valid arrangements. It's worth noting that the space complexity of the code is O(n), as it uses additional arrays to store the visited elements and the rearranged elements.

Approach: Using Set

In this approach, we are using a set data structure (HashSet) to store unique elements from the input array. By iterating over the array and adding each element to the set, it ensures that only distinct elements are retained. It combines the set data structure to obtain unique elements and the priority queue to rearrange the elements based on their frequency. It can be considered as a combination of both set and priority queue approaches.

FileName: UnequalAdjacentEle.java

import java.util.*;
public class UnequalAdjacentEle {
 public static void main(String[] args) {
 int[] array = {2, 3, 3, 4, 5, 5, 6};
 int[] rearrangedArray = rearrangeArray(array);
 if (rearrangedArray != null) {
 System.out.println("Rearranged array: " + Arrays.toString(rearrangedArray));
 } else {
 System.out.println("No valid arrangement exists.");
 }
 }
 public static int[] rearrangeArray(int[] array) {
 // Create a set to store unique elements
 Set<Integer> uniqueSet = new HashSet<>();
 for (int num : array) {
 uniqueSet.add(num);
 }
 // Create a priority queue to store elements based on their frequency
 PriorityQueue<Element> pq = new PriorityQueue<>(Comparator.comparingInt(Element::getFrequency));
 // Count the frequency of each unique element and add it to the priority queue
 for (int num : uniqueSet) {
 int frequency = countFrequency(array, num);
 pq.add(new Element(num, -frequency));
 }
 // Rearrange the array
 StringBuilder sb = new StringBuilder();
 Element prev = null;
 while (!pq.isEmpty()) {
 Element curr = pq.poll();
 sb.append(curr.getValue()).append(" "); // Append the current element to the StringBuilder
 curr.decrementFrequency(); // Decrement the frequency of the current element
 // If the previous element still has a non-zero frequency, add it back to the priority queue
 if (prev != null && prev.getFrequency() < 0) {
 pq.offer(prev);
 }
 prev = curr; // Update the previous element
 }
 // If there are any remaining elements with non-zero frequency, no valid arrangement exists
 if (prev != null && prev.getFrequency() < 0) {
 return null;
 }
 // Convert the StringBuilder to an integer array
 String[] strArr = sb.toString().split(" ");
 int[] rearrangedArray = new int[strArr.length];
 for (int i = 0; i < strArr.length; i++) {
 rearrangedArray[i] = Integer.parseInt(strArr[i]);
 }
 return rearrangedArray;
 }
 // Helper method to count the frequency of an element in the array
 private static int countFrequency(int[] array, int num) {
 int frequency = 0;
 for (int i : array) {
 if (i == num) {
 frequency++;
 }
 }
 return frequency;
 }
 // Class representing an element with its value and frequency
 static class Element {
 private final int value;
 private int frequency;
 public Element(int value, int frequency) {
 this.value = value;
 this.frequency = frequency;
 }
 public int getValue() {
 return value;
 }
 public int getFrequency() {
 return frequency;
 }
 public void decrementFrequency() {
 frequency++;
 }
 }
}

Output:

Rearranged array: [3, 5, 2, 3, 5, 4, 6]

Complexity:

The time complexity of the code is dominated by the sorting operation, resulting in a time complexity of O(n log n). The resulting array requires O(n) space to store the rearranged array as integers. Therefore, the overall space complexity of the code is O(n). In summary, the time complexity of the code is O(n log n), and the space complexity is O(n).sss