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

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

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.