Algorithms for Coding Interviews in Java/

...

/

Solution: Sparse Search

Solution: Sparse Search

In this review lesson, we give a detailed analysis of the solutions for solving the sparse search problem.

We'll cover the following...

Solution #1: Brute force

Press + to interact
class SparseSearch
{   
  public static int searchForString(String[] array, String target)
  {
    //traverse array
    for (int i = 0; i < array.length; i++) {
      //check if current value equals to target string
      if (array[i].equals(target)) {
        //return the index value
        return i;
      }
    }
    return -1;
  }
  public static void main(String args[]) 
  {
    String [] array = {"", "educative", "", "", "",  "hello", "", "learning", "world", "", "", ""};
    String [] targetArray = {"educative", "learning"};
    
    for(int i = 0; i < 2; i++) {
      System.out.println(targetArray[i] + ": " + searchForString(array, targetArray[i]));
    }
  }
}

In this solution, we traverse the entire array of strings and stop only if we find the target string or reach the end of the array.

Time complexity

The time complexity is the time it takes to traverse the entire array, i.e., O ...