Reverse a sentence in Java

Question

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

Answer 1

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;
 }
}

• Anirudh Thatipelli: This code is so elegant. Thanks for sharing it, @Eric Stein.

Answer 2

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();
}

• Eric Stein: +1 for an elegant solution. Depending on the nature of the interview problem, that may or may not count - but it definitely should! OP is working on an online, automated code-submission website. If OP is practicing for the real world, this is definitely the code to use, but it may not pass the automated test framework's performance requirements.
• Mark Jeronimus: I missed that part. But hey, my point still stands. If the performance is bad, then and only then it's time to optimize. If you're in the middle of a timed programming contest, then you're in a whole different league though.
• Anirudh Thatipelli: Thanks for sharing the advice and code @MarkJeronimus. As Eric Stein has rightly mentioned, I am working on an online interview website and preparing for real life coding interviews too. My aim is to keep the code succinct and follow all the java coding conventions.

Answer 3

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.