Java > Array-2 > Coding Bat Problem Given a non-empty array of ints, return a ne

Question

Java > Array-2 > Coding Bat Problem

Given a non-empty array of ints, return a new array containing the elements from the original array that come after the last 4 in the original array. The original array will contain at least one 4. Note that it is valid in java to create an array of length 0.

post4({2, 4, 1, 2}) {1, 2}
post4({4, 1, 4, 2}) {2}
post4({4, 4, 1, 2, 3}) {1, 2, 3}

People on the Internet supposedly are worried about complexity. They say that in order to get a better complexity, there should not be two loops.

So here is the solution that they are not happy with:

public int[] post4(int[] nums) {
   int count = 0;
   for (int i = nums.length - 1; i >= 0; i--) {
       if (nums[i] == 4) {
           count = i;
           break;
       }
  
   }
int[] result = new int[nums.length - (count + 1)];

   for (int i = count + 1, j = 0; i < nums.length; i++, j++) {
       result[j] = nums[i];
   }
return result;
}

and here is the "neat" solution:

public int[] post4(int[] nums) {
int[] result = new int[0];
int j = 0;
   for (int i = 0; i < nums.length; i++) {
       if (nums[i] == 4) {
           result = new int[nums.length - i - 1];
           j = 0;
       } else if (result.length > 0) result[j++] = nums[i];
   }
return result;
}

Please comment on the complexities of the two in the form of Big(O) Notation. Are the people of the web neccessarily correct in saying the first solution is inappropriately implemented because of a supposed higher complexity? Or is the the second, "neat" solution more correct because of a supposed lower complexity and removal of the extra loop?

Explanation / Answer

On the first look the time complexity of the first solution is O(2n) and the second solution is O(n). O(2n) is equivalent to O(n) theoretically, because by definition O(f(n)) = { g | there exist N and c > 0 such that g(n) N }. You can see we multiply a constant in the definition. So O(2n) = O(n) theoretically. In second code a new array is being defined whenever a 4 occurs. This is no so neat in my opinion. If you analyze closely in the first code in the worst case there are n comparisons in the first loop and the second loop starts when the first loop breaks. So the number of comparisons in the first loop + number of copy operations in second loop = n. So overall there are only n operations happening in the first code. In the second code the loop runs n times and each time there it checks a condition and if the "if condition" is true it performs two operations (creates a new array and copy's a values). If the "if condition" fails, then there is a copy operation. So we can assume in each iteration there are atleast two operations happening(one comparison and one copy). So there are 2*n operations happening in the second case. So the first code is actually O(n) and the second case is O(2n). But both are same theoretically. Practically the time difference between the first code and second will be marginal. In my opinion the first solution is neat and easier to understand than the second one.

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---