programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Efficient Array Scanning

Marvin Porte
Greenhorn
Posts: 11
Hello Everyone! Here's another problem I want to discuss with:
Given an array of strings, return a new array without the strings that are equal to the target string. One approach is to count the occurrences of the target string, make a new array of the correct length, and then copy over the correct strings.

wordsWithout({"a", "b", "c", "a"}, "a") → {"b", "c"}
wordsWithout({"a", "b", "c", "a"}, "b") → {"a", "c", "a"}
wordsWithout({"a", "b", "c", "a"}, "c") → {"a", "b", "a"}

Here's my solution:

There is no problem with the code, it works fine and correct with every test. I just want to ask if there's another solution for this that will be more efficient? Because in my solution, I scanned the whole array twice. First is to know the occurences of target in the array and second is to output the array. Is there a way so that I could check the number of occurences and check if it's a target then output the array only in one loop?

Steve Myers
Ranch Hand
Posts: 47
If you can only use arrays, I think you might be able to do it with one loop with java.util.Arrays.copyOf(), copyOfRange() methods. I have my doubts as to whether it would be more efficient.
Otherwise, look at ArrayList.

Winston Gutkowski
Bartender
Posts: 10575
66
Marvin Porte wrote:Is there a way so that I could check the number of occurences and check if it's a target then output the array only in one loop?

Simply put: no. What you could do is to create an array of indexes of non-matching entries, viz:which saves you having to do the comparison twice, but personally I reckon that your way is a lot clearer.

Also, there are other structures, such as a LinkedList, where you don't need to know the output size before you start, so using one of those might be better.

Only worry about efficiency if you know that your code is not fast enough. And you should be able to prove it before you start optimizing.

Winston

Jayesh A Lalwani
Rancher
Posts: 2762
32
Steve Myers wrote:If you can only use arrays, I think you might be able to do it with one loop with java.util.Arrays.copyOf(), copyOfRange() methods. I have my doubts as to whether it would be more efficient.
Otherwise, look at ArrayList.

Internally Arrays.copyOf uses System.arrayCopy so I think it should be pretty fast. Of course, it depends on JVM, but the JVM would probably just copy blocks of memory internally.

Marvin Porte
Greenhorn
Posts: 11
@Sir Steve
No sir, the return type must be an array. I tried arraylist so that there will be no problem with the size but the test in codingbat does not accept arraylist for the solution.

@Sir Winston
Thanks very much again! What I want is to have the simplest solution for a problem and with my answer, I'm not very satisfied and I thought It's very long for that problem. So I consulted here if there's an easier way to solve it. Thanks a lot sir!

@Sir Jayesh
Thank you sir! =D

Steve Myers
Ranch Hand
Posts: 47
Marvin Porte wrote:@Sir Steve
No sir, the return type must be an array. I tried arraylist so that there will be no problem with the size but the test in codingbat does not accept arraylist for the solution.

ArrayList.toArray()

Steve Myers
Ranch Hand
Posts: 47
Check it out it passed the codingBat tests

Joanne Neal
Rancher
Posts: 3742
16
I haven't profiled it but I suspect that the Arrays.copyOf may be a bottleneck there (creating a new array and copying elements into it) so you could reduce it to one call to that method with

Winston Gutkowski
Bartender
Posts: 10575
66
Steve Myers wrote:ArrayList.toArray()

Or indeed, any List.toArray(). Winston

Marvin Porte
Greenhorn
Posts: 11
To ALL:
Thanks everyone for alternative solutions, I really appreciate it. You know I'm only a beginner and don't know anything aside from basic syntax and my logic. Maybe I should start reading API docs so I could use helpful methods for my solutions next time. Thanks a lot! =D