Find The Duplicates in two arrays

Question

Find The Duplicates

Given two sorted arrays arr1 and arr2 of passport numbers, implement a function findDuplicates that returns an array of all passport numbers that are both in arr1 and arr2. Note that the output array should be sorted in an ascending order.

Let N and M be the lengths of arr1 and arr2, respectively. Solve for two cases and analyze the time & space complexities of your solutions: M ≈ N - the array lengths are approximately the same M ≫ N - arr2 is much bigger than arr1.

My approach:

import java.io.*;
import java.util.*;
import java.lang.*;

class Solution {

  static int[] findDuplicates(int[] arr1, int[] arr2) {
    // your code goes here
    int i = 0, j = 0, k = 0;
    ArrayList<Integer> ans = new ArrayList<>();
    while(( i < arr1.length) && (j < arr2.length))
    {
      if(arr1[i] < arr2[j])
          i++;
      else if(arr1[i] == arr2[j])
      {
          ans.add(arr1[i]);
          k++;
          i++;
          j++;
      }
      else
          j++;
     }
    int[] arr = new int[ans.size()];

    for(int l = 0; l < ans.size(); l++) {
    if (ans.get(l) != null) {
        arr[l] = ans.get(l);
    }
}
    return arr;
  }
   //M = arr1.length, N = arr2.length        
  //Time = O(M+N)
  //Space = O(min(M,N))

I have the following questions regarding my code:

1) How can I improve the time and space complexity of my code?

2) Is there a better way(lesser lines of code, better data structures) that can be used to improve the code?

Source: Mock interview

Answer 1

I'd say the code suffers from readability more than from the efficiency aspects you (or your interviewer) had in mind.

The problem with such performance centric code is that usually the time spend to create and optimize the solution exceeds the time possibly saved during runtime of the program summed up over its lifetime by magnitudes.

And at the end it doesn't not tell something about your skills as a Java programmer. But thats the problem of your interviewer...

1) How can I improve the time and space complexity of my code?

removing unused variables would be a first step. You declare and increment k but you never read it. But agreed, this is not a "killer"...

2) Is there a better way(lesser lines of code, better data structures) that can be used to improve the code?

The pure LoC metric has no meaning. The most important property of code (after correctness) is readability. Structuring your code in to small methods with distinct responsibilities and well chosen names is a much higher value then LoC, but its mot measurable...

so here is my suggestion. Especially look at the content of the for loop how that makes a description of my intention what the code is supposed to do:

import java.util.ArrayList;
import java.util.List;
class Solution {
    static int[] findDuplicates(int[] arr1, int[] arr2) {
        List<Integer> ans = selectDuplicates(//
                arr1.length < arr2.length ? arr1 : arr2, // shorter
                arr1.length < arr2.length ? arr2 : arr1);// longer
        return convertToIntArray(ans);
    }

    private static List<Integer> selectDuplicates(int[] shorter, int[] longer) {
        ArrayList<Integer> duplicates = new ArrayList<>();
        int indexInLonger = 0;
        for (int current : shorter) {
            indexInLonger = seekToEqualOrBiggerIn(longer, current, indexInLonger);
            addMatchTo(duplicates, current, longer[indexInLonger]);
        }
        return duplicates;
    }

    private static int seekToEqualOrBiggerIn(int[] longer, int current, int indexInLonger) {
        while (longer.length > indexInLonger && current > longer[indexInLonger])
            indexInLonger++;
        return indexInLonger;
    }

    private static void addMatchTo(ArrayList<Integer> duplicates, int current, int possibleMatch) {
        if (current == possibleMatch)
            duplicates.add(current);
    }

    private static int[] convertToIntArray(List<Integer> ans) {
        return ans.stream().mapToInt(item -> item.intValue()).toArray();
    }
}

---

selectDuplicates() forces the caller to check the length of the arrays? – Sharon Ben Asher

selectDuplicates() is a private method, an implementation detail not meant to be called by anyone else. So no caller is "forced" to check the length.

why? – Sharon Ben Asher It is an optimization.

The idea is that I do things fastest when I don't do them.

With this optimization the length of the shorter array is implicitly checked by the foreach loop. It saves me from incrementing and checking both indexed during the iteration.

It also reduces the iterations to the size of the smaller array since the bigger array must have some entries not in the smaller array.

this is an internal implementation that is meaningful only to the method and not the caller. – Sharon Ben Asher

Exactly! Thats why it is i my implementation not exposed to the outside.

and it doesn't even check if it got the correct arguments. – Sharon Ben Asher

what would a "correct" argument look like in your opinion?

it should be able to accept any two arrays sort out which is shorter than which. you chould have a shorter() and longer() methods that do the actual checking and have selectDuplicates() call them.... – Sharon Ben Asher

The method findDuplicates() which is the public interface does exactly that.

I also don't like the name of the methods. seekToEqualOrBiggerIn() is way too implementation-specific.

But that is the main purpose of a private methods name: describe the current behavior of that method as detailed as possible.

what if the input is ordered in reverse? sure you will have to modify the code inside the method but the intention of the method remains the same: skip elements that are have "lower" order according to the order of the arrays. – Sharon Ben Asherand

The OPs requirement explicitly mentioned ascending order. According to the YAGNY-principly I should not provide anticipated but not required flexibility. IMHO this also applies to naming too.

In fact if the requirement would change this name would actually make easier to find the part to change while skimming over the code. Of cause it would be renamed then.

also, addMatchTo() does not hint that the match is not yet certain and that a condition is applied. – Sharon Ben Asher

At least to me it does. And no question: The receiver of a message determines its content.

and I don't understand the reason for this particular breaking up of the code into methods. why do you have findDuplicates() and selectDuplicates() ? this seems arbitrary separation.

findDuplicates() is part of the public API (fixed by the interviewer I guess).

The OPs implementation consist of two logical parts:

1. find and collect the duplicates in a list
2. convert that list into an array as expected by the methods signature.

To me this are two different responsibilities which should live in their own methods according the the single responsibility principle.

Since Java does not allow methods signatures to differ only in the return value I needed a different but similar name.

Answer 2

Here are my comments:

1. The variable k was probably meant to keep track of size of the array list (number of duplicates). However, it is redundant, since you use the list's size() method.

2. To convert a list to array you can use the stream API. while I am not certain if it provides any time/space benefits, it is probably the most optimized way to do it, and it saves you having to declare the return array. Since it is tricky to do the conversion with primitive types arrays, here it is: ans.stream().mapToInt(item -> item.intValue()).toArray(); and you can make it the return value of the method.

3. The while condition is using redundant parentheses that have the && between them . It can be argued as a matter of taste, but in my eyes, the condition is clearer without them. I add an additional space around the higher order operator: while(i < arr1.length && j < arr2.length)

Answer 3

If I were scoring this code, I would mark down for the following:

    int i = 0, j = 0, k = 0;

I would split these up onto multiple lines. Either

    int i = 0,
        j = 0, 
        k = 0;

Or I'd actually prefer

    int i = 0;
    int j = 0;

As others have noted k is redundant.

I would only use commas if I were writing this as a for loop.

    for (int i = 0, j = 0; i < arr1.length && j < arr2.length; ) {

I'd prefer separate statements otherwise.

    ArrayList<Integer> ans = new ArrayList<>();

Two things.

    List<Integer> answer = new ArrayList<>();

As a simple matter of habit, I would declare the variable as type List. It doesn't make much difference here, but it's a good habit to have. I would mark down for not having it.

There seems no reason to abbreviate answer to ans. Saving three letters now versus the cognitive dissonance of having to work it out every time someone reads it? I'd rather see developers spend the three letters. It's in a good cause.

      if(arr1[i] < arr2[j])

Two things again.

      if (arr1[i] < arr2[j]) {

I prefer to always use a space between keywords like if and while and the subsequent parenthesis. This helps me differentiate keywords from method calls, so I can read the code faster.

I always use the block form of control structures rather than the single statement form. For one thing, it saves having to think about whether the single statement form would work (there are times when it doesn't). And in this particular case, the blow to readability from switching between the single statement form and the block form kills it for me.

These aren't necessarily wrong. Perhaps someone else would mark down my versions instead. But I believe that my versions better fit the Java standard.

Answer 4

In addition to the other answers:

Don't use wildcard imports like import java.util.*;. Imagine, in some future Java version, Oracle adds a class into the java.util package that collides with some class that you already use. You then end up with a name collision. Only use individual imports for single classes.

An import like import java.lang.*; shows a lack of knowledge about the Java naming system. Classes from java.lang are always accessible with their simple name, not needing an import statement.

So, your solution shows that you got the algorithm right (it's well known, so not very hard), but are a Java newbie and don't care very much about style.

This solution wouldn't help you to get the job as Java developer - only as a trainee.

Answer 5

class Solution {

  public static int[] findDuplicates(int[] arr1, int[] arr2) {
    if (arr1 == null || arr2 == null) {
      throw NPE();
    }

    int i = 0, j = 0;
    final List<Integer> ans = new ArrayList<>();
    while((i < arr1.length) && (j < arr2.length)) {
      if(arr1[i] < arr2[j]) {
          i++;
     } else if(arr1[i] == arr2[j]) {
          ans.add(arr1[i]);
          i++;
          j++;
      }
      else {
          j++;
     }

    return list.stream().toArray(int[]::new);
  }

Cleaned up a bit. Added some verification / java 8 / unused 'k' variable