1
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • \$\begingroup\$ This code is so elegant. Thanks for sharing it, @Eric Stein. \$\endgroup\$ – Anirudh Thatipelli Jun 6 '18 at 17:25
4
\$\begingroup\$

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();
}
\$\endgroup\$
  • \$\begingroup\$ +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. \$\endgroup\$ – Eric Stein Jun 7 '18 at 10:34
  • \$\begingroup\$ 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. \$\endgroup\$ – Mark Jeronimus Jun 7 '18 at 11:22
  • \$\begingroup\$ 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. \$\endgroup\$ – Anirudh Thatipelli Jun 8 '18 at 9:59
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.