Array mutation without extra space

Question

In an interview, I was asked the following question, and I could not find a solution.

This array is an array of character length n and the "important section" (all characters in this section must be stored) length m , where n> = m> = 0 as follows:

Without additional space, complete the following process:
Delete all occurrences of A and duplicate all occurrences of B , return an additional array of mutated array. For example, for the above array [C,A,X,B,B,F,Q] n = 7, m = 5, the output will be [C,X,B,B,B,B] . Note that the length of the mutated array is 6, since Q is in the backup partition and B is duplicated.

Return -1 if the operation cannot be completed.

Examples:

 n=2, m=2 , [A,B] => [B,B] n=2, m=2 , [B,B] => -1 (since the result [B,B,B,B] is larger then the array) n=3, m=2 , [A,B,C] => [B,B] n=3, m=3 , [A,B,C] => [B,B,C] n=3, m=2 , [Z,B,A] => [Z,B,B] (since A was in the redundant section) 

We are looking for an example code. Can this be done in O (n) time complexity?

Answer 1

The code with some optimizations will look something like this: O (n):

 // returns length of the relevant part of the mutated array or -1 public static int mutate(char[] a, int m) { // delete As and count Bs in the relevant part int bCount = 0, position = 0; for (int i = 0; i < m; i++) { if (a[i] != 'A') { if (a[i] == 'B') bCount++; a[position++] = a[i]; } } // check if it is possible int n = bCount + position; if (n > a.length) return -1; // duplicate the Bs in the relevant part for (int i = position - 1, index = n - 1; i >= 0; i--) { if (a[i] != 'B') { a[index--] = a[i]; } else { a[index--] = 'B'; a[index--] = 'B'; } } return n; } 

Answer 2

• Scan the array to determine if it is possible to store the mutated array in accessible space - count A and B , and check NM >= numB-numA
• Go through the array from left to right: shift the elements from the left by the number A so far (place of filling A)
• Pass the array from right to left: move the elements to the right by numB-B_so_far , adding additional B s

Answer 3

Start at the end of the input array. We will find out on the back what needs to be filled.

Look at the last significant character at the input (position m ). If it is a , ignore it. Otherwise, add a character. Repeat until you read all of the input.

This removes a s. Now we will duplicate b s.

Start at the beginning of the array. Find the last value you wrote during the above steps. If it is b , write two b s. If this is something else, just write one of them. Reiteration. NOTE. If you ever “catch up”, you need to write where you need to read, you do not have enough space, and you exit -1 . Otherwise, return part of the array from position 1 to the last reading position.

Example:

 Phase 1: removing A CAXBBFQ CAXBBFB CAXBBBB CAXBXBB CAXCXBB Phase 2: duplicating B CAXCXBB CXXCXBB CXBBXBB CXBBBBB ^^^^^^ 

Phase 1 is linear (we read the characters m and write no more than m ).

Phase 2 is linear (we read fewer m characters and write no more than 2m ).

m less than n ; therefore, all O(m) and O(n) .