Reverse a sentence in Java 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 &lt; 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 &lt; 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 &gt;= 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;
    }
}