hashmap.get() == operator returning false

Question

I'm working on the following problem:

Gary is an avid hiker. He tracks his hikes meticulously, paying close attention to small details like topography. During his last hike he took exactly n steps.

For every step he took, he noted if it was an uphill, U, or a downhill, D step. Gary's hikes start and end at sea level and each step up or down represents a 1 unit change in altitude. We define the following terms:

A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level.

A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level. Given Gary's sequence of up and down steps during his last hike, find and print the number of valleys he walked through.

For example, if Gary's path is s = [DDUUUUDD], he first enters a valley 2 units deep. Then he climbs out an up onto a mountain 2 units high. Finally, he returns to sea level and ends his hike.

Function Description

Complete the countingValleys function in the editor below. It must return an integer that denotes the number of valleys Gary traversed.

countingValleys has the following parameter(s):

n: the number of steps Gary takes

s: a string describing his path Input Format

The first line contains an integer , the number of steps in Gary's hike. The second line contains a single string , of characters that describe his path.

Output Format

Print a single integer that denotes the number of valleys Gary walked through during his hike.

Sample Input

8 UDDDUDUU

Sample Output

1

Below is my implementation in java. It works for the small test cases but not for the big ones.

static int countingValleys(int n, String s) {


  //Use a hashmap to keep track of the number of moves.
  HashMap<Character,Integer> map = new HashMap();

  boolean sea = true;//check if we are at sea level

  //if both D and U have the same total no, we are at sea level.
  map.put('D',0);
  map.put('U',0);

  int valleys = 0;//count num of valleys

  for(int i = 0; i < n; i++){
      char key = s.charAt(i);

      //check if we are at sea level
      if(map.get('D') == map.get('U')){//<--PROBLEM
          sea = true;
      }
      else
          sea = false;

      if(sea == true && key == 'D'){//if we are at sea level and our next key is D, we have a valley

          valleys += 1;
      }

      map.put(key,map.get(key) + 1);//add move and update our hashmap   
  }

  return valleys;

}

The problem seems to be at "if(map.get('D') == map.get('U'))", it seems to be returning false for big numbers, can someone tell me why? It works if I assign each map.get() to a variable and compare the variables instead.

I also wrote the exact same thing in javascript using the "new Object()" type and it passed all the test cases, but it is not working in java with hashmap, why is that?

link to original problem - https://www.hackerrank.com/challenges/counting-valleys/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup

Answer 1

First, as mentioned in other answer, use .equals() instead of == in this case. An even better approach is, you don't even need to use a Map. Just one integer will be good enough.

As your question is ...returning false for big numbers, can someone tell me why?

Here is the reason.

There are several things you need to understand

1. Types of variable

First, you need to know there are two types of variable in Java: Primitive and Reference.

An integer is usually a Primitive, so the variable itself is the integer value: int a = 1234; : a itself is having value 1234.

To compare primitive variable, you should use ==

For reference type, variable itself is a "pointer". In Java there are Wrapper Classes for primitives. For example, Integer is the wrapper for int. So in Integer a = new Integer(1234);, a is not containing value of 1234. It is a pointer pointing to an Integer object reference. Using == on reference type variables does not compare the content, but only check if the pointer value is the same (i.e. check if they point to same object instance)

2. Autoboxing

Starting from Java 1.5 (iirc), there is a feature called auto-boxing (and unboxing), which ease programmer in converting between primitive types and their corresponding wrapper.

In the past, you need to do something like this:

int a = 1234;
Integer intWrapper = new Integer(a);

int b = intWrapper.intValue();

With autoboxing, you just need to write:

int a = 1234;
Integer intWrapper = a;
int b = intWrapper;

And compiler is going to convert it to:

int a = 1234;
Integer intWrapper = Integer.valueOf(a);
int b = intWrapper.intValue();

So far so good?

Final Answer

So the reason why your code works with small number is: Integer.valueOf() is caching frequently-used value. From API doc:

public static Integer valueOf(int i)

Returns an Integer instance representing the specified int value. If a new Integer instance is not required, this method should generally be used in preference to the constructor Integer(int), as this method is likely to yield significantly better space and time performance by caching frequently requested values. This method will always cache values in the range -128 to 127, inclusive, and may cache other values outside of this range.

Because it is caching the wrappers, therefore if you are doing map.put(key,map.get(key) + 1), result of get(key) + 1, which is an int, when converting to Integer and if it is a small number, will be a same instance of Integer for same int value. That means, == still works (as variables are pointing to same Integer). However if it is a not-cached number, every invocation will be a different instance, and == will not work (as variables are pointing to different instances of Integer, though the value in the Integer instances are the same)

---

Suggestion to your algorithm, though a bit off topic:

Your logic is over complicated. It can be greatly simplified to (pseudo code):

countValley(String s) {
    currentLevel = 0
    valleyCount = 0
    for (step in s) {
        if step == 'U' {
            ++currentLevel;
            if (currentLevel == 0) {  // returning to sea level
                ++valleyCount
            }
        } else if step == 'D' {
            --currentLevel;
        }
    }
    return valleyCount
}        

Answer 2

to compare wrapper Class need to use .equals. can use Objects.equals :

java.util.Objects.equals(firstInteger, secondInteger);

for case above :

if(java.util.Objects.equals(map.get('D'), map.get('U'))){
   sea = true;
}

Answer 3

First, don't use '=='. Use .equals for all classes extends Object.

Answer 4

to compare content of wrapper classes (Integer, Float, Long, Double), use .equals(). "==" would compare the references of both objects. The references might be different even though both contain the same content. You will can however use "==" when you are comparing value types such as int, float, long, double.

Answer 5

1. Solution 1: If you must use a HashMap, looks like iteration in HashMap is the problem. Below a link to how to do it. As you iterate, build your logic for counting hills and valleys. How to efficiently iterate over each entry in a Java Map?.

Solution 2: Use Array instead of HashMap. After building it, find the D sequences and so on.