trjhtr

You are given an array of characters arr that consists of sequences of characters separated by space characters. Each space-delimited sequence of characters defines a word.

Implement a function reverseWords that reverses the order of the words in the array in the most efficient manner.

Explain your solution and analyze its time and space complexities.

Example:

input: arr = [ 'p', 'e', 'r', 'f', 'e', 'c', 't', ' ',
 'm', 'a', 'k', 'e', 's', ' ',
 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' ]

output: [ 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e', ' ',
 'm', 'a', 'k', 'e', 's', ' ',
 'p', 'e', 'r', 'f', 'e', 'c', 't' ]

Constraints:

[time limit] 5000ms

[input] array.character arr

0 ≤ arr.length ≤ 100
[output] array.character

My approach:

import java.io.*;

import java.util.*;

class Solution 

 static void reverseAword(char arr, int start, int end)
 
 int len = end - start + 1;
 for( int i = start, j = end; i < len/2; i++,j-- )
 
 char temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 
 

 static char reverseWords(char arr) 
 // your code goes here
 int len = arr.length;

 //Reverse the complete sentence
 reverseAword(arr,0,len - 1);

 int start = 0;
 for( int i = 0; i < len; i++)
 
 //If there is a space, reverse the word from start till index - 1( before ' ')
 if( arr[i] == ' ' )
 
 if( start == 0 )
 
 reverseAword(arr,start,i - 1);
 start = 0;
 
 
 else if( i == len - 1)
 
 if( start != 0)
 reverseAword(arr, start,i);
 
 else
 
 if( start == 0)
 start = i;
 

 

 return arr;
 

 public static void main(String args) 

 char c1 = ' ', ' '; 
 c1 = reverseWords(c1);

 System.out.println(Arrays.toString(c1));
 

I have the following questions with respect to the above code:

1) How can I further improve the time and space complexity?

2) Can this problem be solved using a smarter way?

3) Are there too many redundant variables that we are better off with?

Reference

You can improve time complexity by doubling the space complexity. If you don't modify the input array in place (which is probably a bad idea in real code anyway), you can use System.arraycopy instead of repeatedly reversing parts of the char. I also think that would be easier to read. That approach might look something like:

import java.util.Arrays;

public final class Solution 

 private static final char INPUT =
 new char 
 'p', 'e', 'r', 'f', 'e', 'c', 't', ' ',
 'm', 'a', 'k', 'e', 's', ' ',
 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' ;

 private static final char OUTPUT =
 new char 
 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e', ' ',
 'm', 'a', 'k', 'e', 's', ' ',
 'p', 'e', 'r', 'f', 'e', 'c', 't' ;


 public static void main(final String argv) 
 System.out.println(Arrays.equals(OUTPUT, reverseWords(INPUT)));
 

 private static char reverseWords(final char input) 
 final char output = new char[input.length];
 int outputIndex = 0;
 int lastSpaceIndex = input.length;
 for (int i = input.length - 1; i >= 0; i--) 
 if (input[i] == ' ') 
 final int length = lastSpaceIndex - (i + 1);
 System.arraycopy(input, i + 1, output, outputIndex, length);
 output[outputIndex + length] = ' ';
 outputIndex += length + 1;
 lastSpaceIndex = i;
 
 
 System.arraycopy(input, 0, output, outputIndex, lastSpaceIndex);
 return output;
 

This solution sacrifices both time and space, for a very readable solution. In practice it's bad to prematurely optimize and always good to maximize readability before starting to optimize.

static char reverseWords(char arr) 
 String sentence = String.valueOf(arr);
 List<String> words = Arrays.asList(sentence.split(" "));

 Collections.reverse(words);

 return String.join(" ", words).toCharArray();

With regard to 1) : No, it can't. You algorithm already works in-place and O(n), so it is impossible to improve the time or space complexity, at most you can improve constant factors. I argue that the lower time complexity bound is O(n) because at the very least, you have to look at the complete array to find all the spaces.