-1

I'm doing a problem on hackerRank and the problem is:

Problem Statement

Here we have to count the number of valleys does XYZ person visits.

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.

For One step up it U, and one step down it is D. We will be given the number of steps does XYZ person traveled plus the ups and down in the form of string, i.e,

UUDDUDUDDUU

Sample Input

8
UDDDUDUU

Sample Output

1

Explanation

If we represent _ as sea level, a step up as /, and a step down as \, Gary's hike can be drawn as:

_/\      _
   \    /
    \/\/

He enters and leaves one valley.

The code I wrote doesn't work

static int countingValleys(int n, String s) {    
    int count = 0;
    int level = 0;
    String[] arr = s.split("");
    for(int i = 0; i<n;i++){
        if(arr[i] == "U"){
            level++;
        } else{
            level--;
        }    
        if(level==0 && arr[i]=="U"){
            count++;
        }
    }
    return count;
}

But another solution I found does, however no matter how I look at it the logic is the same as mine:

static int countingValleys(int n, String s) {
    int v = 0;     // # of valleys
    int lvl = 0;   // current level
    for(char c : s.toCharArray()){
        if(c == 'U') ++lvl;
        if(c == 'D') --lvl;

        // if we just came UP to sea level
        if(lvl == 0 && c == 'U')
            ++v;
    }
    return v;
}

So what's the difference I'm missing here that causes mine to not work? Thanks.

smac89
  • 39,374
  • 15
  • 132
  • 179
Dennis Liu
  • 43
  • 5
  • In the second example, they are using `char`'s, so `==` is ok. You are using `String`'s, which are objects. This means you have to compare them with `.equals` – GBlodgett May 13 '19 at 17:03
  • First, use `String[] arr = s.toCharArray()` instead of `String[] arr = s.split("");`. I think it will be more efficient. Second, for your level (level of the sea), increase when `c=='U'` and then check to see if `c=='D'` and decrease. – acarlstein May 13 '19 at 17:04
  • 1
    See this lovely [debug](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) blog for help. A simple set of `print` statements to trace program operation would point up the problem. – Prune May 13 '19 at 17:25

1 Answers1

2

In java, you need to do this to compare String values:

        if("U".equals (arr[i])) {

And not this:

        if(arr[i] == "U") {

The former compares the value "U" to the contents of arr[i].

The latter checks whether the strings reference the same content or more precisely the same instance of an object. You could think of this as do they refer to the same block of memory? The answer, in this case, is they do not.

To address the other aspect of your question.

Why this works:

for(char c : s.toCharArray()){
        if(c == 'U') ++lvl;
        if(c == 'D') --lvl;

when this does not:

    String[] arr = s.split("");
    for(int i = 0; i<n;i++){
        if(arr[i] == "U"){

You state that the logic is the same. Hmmmm, maybe, but the data types are not.

In the first version, the string s is split into an array of character values. These are primitive values (i.e. an array of values of a primitive data type) - just like numbers are (ignoring autoboxing for a moment). Since character values are primitive types, the value in arr[i] is compared by the == operator. Thus arr[i] == 'U' (or "is the primitive character value in arr[i] equal to the literal value 'U') results in true if arr[i] happens to contain the letter 'U'.

In the second version, the string s is split into an array of strings. This is an array of instances (or more precisely, an array of references to instances) of String objects. In this case the == operator compares the reference values (you might think of this as a pointer to the two strings). In this case, the value of arr[i] (i.e. the reference to the string) is compared to the reference to the string literal "U" (or "D"). Thus arr[i] == "U" (or "is the reference value in arr[i] equal to the reference value of where the String instance containing a "U" string" is located) is false because these two strings are in different locations in memory.

As mentioned above, since they are different instances of String objects the == test is false (the fact that they just happen to contain the same value is irrelevant in Java because the == operator doesn't look at the content). Hence the need for the various equals, equalsIgnoreCase and some other methods associated with the String class that define exactly how you wish to "compare" the two string values. At risk of confusing you further, you could consider a "reference" or "pointer" to be a primitive data type, and thus, the behaviour of == is entirely consistent.

If this doesn't make sense, then think about it in terms of other object types. For example, consider a Person class which maybe has name, date of birth and zip/postcode attributes. If two instances of Person happen to have the same name, DOB and zip/postcode, does that mean that they are the same Person? Maybe, but it could also mean that they are two different people that just happen to have the same name, same date of birth and just happen to live in the same suburb. While unlikely, it definitely does happen.

FWIW, the behaviour of == in Java is the same behaviour as == in 'C'. For better or worse, right or wrong, this is the behaviour that the Java designers chose for == in Java.

It is worthy to note that other languages, e.g. Scala, define the == operator for Strings (again rightly or wrongly, for better or worse) to perform a comparison of the values of the strings via the == operator. So, in theory, if you addressed other syntactic issues, your arr[i] == "U" test would work in Scala. It all boils down to understanding the rules that the various operators and methods implement.

Going back to the Person example, assume Person was defined as a case class in Scala. If we created two instances of Person with the same name, DOB and zip/postcode (e.g. p1 and p2), then p1 == p2 would be true (in Scala). To perform a reference comparison (i.e. are p1 and p2 instances of the same object), we would need to use p1.eq(p2) (which would result in false).

Hopefully the Scala reference, does not create additional confusion. If it does, then simply think of it as the function of an operator (or method) is defined by the designers of the language / library that you are using and you need to understand what their rules are.

At the time Java was designed, C was prevalent, so it can be argued that it makes sense the C like behaviour of == replicated in Java was a good choice at that time. As time has moved on, more people think that == should be a value comparison and thus some languages have implemented it that way.

GMc
  • 1,764
  • 1
  • 8
  • 26
  • Dennis, did this help you with your question? If so,can you please accept the answer? Just click on the grey check mark next to the answer. Thanks – GMc May 15 '19 at 02:19