Find Maximun area on Array
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
I am doing exercises from the app Data Structures in Scala, I have coded the second problem on Arrays like this:
/**
* Given n non-negative integers a1, a2, ..., an, where each represents a
* point at coordinate (i, ai), n vertical lines are drawn such that
* the two endpoints of line i is at (i, ai) and (i, 0).
*
* Find two lines, which together with x-axis forms a container such
* that the container contains the most water.
*
* Efficiency: O(n)
*
* @param a Array of line heights
* @return Maximum area
*/
def maxArea(a: Array[Int]): Int = {
@tailrec
def go(l: Int, r: Int)(max: Int): Int = {
if (l >= r) max
else {
val currArea = math.min(a(l), a(r)) * (r - l)
val area = math.max(max, currArea)
log debug s"Current area for $l and $r is $currArea"
log debug s"Max area till now is $area"
if (a(l) < a(r)) go(l + 1, r)(area)
else go(l, r - 1)(area)
}
}
go(0, a.size - 1)(0)
}
I wonder if there is a better alternative to write recursive functions as a way of looping through the Array, as someone once told me calls recursion the GOTO of functional programming.
You can check the complete source code at GitHub
Thank you in advance.
arrays scala performance data-structures
asked Nov 16 '18 at 17:36
ElBaulPElBaulP
2,90932049
add a comment |
I am doing exercises from the app Data Structures in Scala, I have coded the second problem on Arrays like this:
/**
* Given n non-negative integers a1, a2, ..., an, where each represents a
* point at coordinate (i, ai), n vertical lines are drawn such that
* the two endpoints of line i is at (i, ai) and (i, 0).
*
* Find two lines, which together with x-axis forms a container such
* that the container contains the most water.
*
* Efficiency: O(n)
*
* @param a Array of line heights
* @return Maximum area
*/
def maxArea(a: Array[Int]): Int = {
@tailrec
def go(l: Int, r: Int)(max: Int): Int = {
if (l >= r) max
else {
val currArea = math.min(a(l), a(r)) * (r - l)
val area = math.max(max, currArea)
log debug s"Current area for $l and $r is $currArea"
log debug s"Max area till now is $area"
if (a(l) < a(r)) go(l + 1, r)(area)
else go(l, r - 1)(area)
}
}
go(0, a.size - 1)(0)
}
I wonder if there is a better alternative to write recursive functions as a way of looping through the Array, as someone once told me calls recursion the GOTO of functional programming.
You can check the complete source code at GitHub
Thank you in advance.
arrays scala performance data-structures
asked Nov 16 '18 at 17:36
ElBaulPElBaulP
2,90932049
Re recursion/goto, for those interested, the related paper
– Lasf
Nov 16 '18 at 20:14
@eukaryota Removed
– ElBaulP
Nov 17 '18 at 14:35
add a comment |
I am doing exercises from the app Data Structures in Scala, I have coded the second problem on Arrays like this:
/**
* Given n non-negative integers a1, a2, ..., an, where each represents a
* point at coordinate (i, ai), n vertical lines are drawn such that
* the two endpoints of line i is at (i, ai) and (i, 0).
*
* Find two lines, which together with x-axis forms a container such
* that the container contains the most water.
*
* Efficiency: O(n)
*
* @param a Array of line heights
* @return Maximum area
*/
def maxArea(a: Array[Int]): Int = {
@tailrec
def go(l: Int, r: Int)(max: Int): Int = {
if (l >= r) max
else {
val currArea = math.min(a(l), a(r)) * (r - l)
val area = math.max(max, currArea)
log debug s"Current area for $l and $r is $currArea"
log debug s"Max area till now is $area"
if (a(l) < a(r)) go(l + 1, r)(area)
else go(l, r - 1)(area)
}
}
go(0, a.size - 1)(0)
}
I wonder if there is a better alternative to write recursive functions as a way of looping through the Array, as someone once told me calls recursion the GOTO of functional programming.
You can check the complete source code at GitHub
Thank you in advance.
arrays scala performance data-structures
asked Nov 16 '18 at 17:36
ElBaulPElBaulP
2,90932049
I am doing exercises from the app Data Structures in Scala, I have coded the second problem on Arrays like this:
/**
* Given n non-negative integers a1, a2, ..., an, where each represents a
* point at coordinate (i, ai), n vertical lines are drawn such that
* the two endpoints of line i is at (i, ai) and (i, 0).
*
* Find two lines, which together with x-axis forms a container such
* that the container contains the most water.
*
* Efficiency: O(n)
*
* @param a Array of line heights
* @return Maximum area
*/
def maxArea(a: Array[Int]): Int = {
@tailrec
def go(l: Int, r: Int)(max: Int): Int = {
if (l >= r) max
else {
val currArea = math.min(a(l), a(r)) * (r - l)
val area = math.max(max, currArea)
log debug s"Current area for $l and $r is $currArea"
log debug s"Max area till now is $area"
if (a(l) < a(r)) go(l + 1, r)(area)
else go(l, r - 1)(area)
}
}
go(0, a.size - 1)(0)
}
I wonder if there is a better alternative to write recursive functions as a way of looping through the Array, as someone once told me calls recursion the GOTO of functional programming.
You can check the complete source code at GitHub
Thank you in advance.
arrays scala performance data-structures
arrays scala performance data-structures
asked Nov 16 '18 at 17:36
ElBaulPElBaulP
2,90932049
asked Nov 16 '18 at 17:36
ElBaulPElBaulP
2,90932049
edited Nov 17 '18 at 14:34
ElBaulP
asked Nov 16 '18 at 17:36
ElBaulPElBaulP
2,90932049
asked Nov 16 '18 at 17:36
ElBaulPElBaulP
2,90932049
asked Nov 16 '18 at 17:36
ElBaulPElBaulP
2,90932049
2,90932049
Re recursion/goto, for those interested, the related paper
– Lasf
Nov 16 '18 at 20:14
@eukaryota Removed
– ElBaulP
Nov 17 '18 at 14:35
add a comment |
Re recursion/goto, for those interested, the related paper
– Lasf
Nov 16 '18 at 20:14
@eukaryota Removed
– ElBaulP
Nov 17 '18 at 14:35
Re recursion/goto, for those interested, the related paper
– Lasf
Nov 16 '18 at 20:14
Re recursion/goto, for those interested, the related paper
– Lasf
Nov 16 '18 at 20:14
@eukaryota Removed
– ElBaulP
Nov 17 '18 at 14:35
@eukaryota Removed
– ElBaulP
Nov 17 '18 at 14:35
add a comment |
1 Answer
1
active
oldest
votes
Here's a way to implement your algorithm without recursion (not that I actually think there's anything inherently wrong with recursion).
def maxArea2(a: Array[Int]): Int = {
Stream.iterate(0 -> a){ case (_, arr) =>
if (arr.length < 2) -1 -> arr
else {
val (lft, rght) = (arr.head, arr.last)
val area = (lft min rght) * (arr.length - 1)
if (lft <= rght) area -> arr.dropWhile(_ <= lft)
else area -> arr.reverse.dropWhile(_ <= rght)
}
}.takeWhile(_._1 >= 0).maxBy(_._1)._1
}
The idea is to iterate lazily and the take (i.e. realize) only those you need.
You'll note that this iterates, and calculates areas, fewer times because it drops values that can't beat the current area calculation.
answered Nov 16 '18 at 20:42
jwvhjwvh
28.6k52142
Thanks!, so it seems this approach would be more efficient?
– ElBaulP
Nov 17 '18 at 14:36
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53342810%2ffind-maximun-area-on-array%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Here's a way to implement your algorithm without recursion (not that I actually think there's anything inherently wrong with recursion).
def maxArea2(a: Array[Int]): Int = {
Stream.iterate(0 -> a){ case (_, arr) =>
if (arr.length < 2) -1 -> arr
else {
val (lft, rght) = (arr.head, arr.last)
val area = (lft min rght) * (arr.length - 1)
if (lft <= rght) area -> arr.dropWhile(_ <= lft)
else area -> arr.reverse.dropWhile(_ <= rght)
}
}.takeWhile(_._1 >= 0).maxBy(_._1)._1
}
The idea is to iterate lazily and the take (i.e. realize) only those you need.
You'll note that this iterates, and calculates areas, fewer times because it drops values that can't beat the current area calculation.
answered Nov 16 '18 at 20:42
jwvhjwvh
28.6k52142
Thanks!, so it seems this approach would be more efficient?
– ElBaulP
Nov 17 '18 at 14:36
add a comment |
Here's a way to implement your algorithm without recursion (not that I actually think there's anything inherently wrong with recursion).
def maxArea2(a: Array[Int]): Int = {
Stream.iterate(0 -> a){ case (_, arr) =>
if (arr.length < 2) -1 -> arr
else {
val (lft, rght) = (arr.head, arr.last)
val area = (lft min rght) * (arr.length - 1)
if (lft <= rght) area -> arr.dropWhile(_ <= lft)
else area -> arr.reverse.dropWhile(_ <= rght)
}
}.takeWhile(_._1 >= 0).maxBy(_._1)._1
}
The idea is to iterate lazily and the take (i.e. realize) only those you need.
You'll note that this iterates, and calculates areas, fewer times because it drops values that can't beat the current area calculation.
answered Nov 16 '18 at 20:42
jwvhjwvh
28.6k52142
Thanks!, so it seems this approach would be more efficient?
– ElBaulP
Nov 17 '18 at 14:36
add a comment |
Here's a way to implement your algorithm without recursion (not that I actually think there's anything inherently wrong with recursion).
def maxArea2(a: Array[Int]): Int = {
Stream.iterate(0 -> a){ case (_, arr) =>
if (arr.length < 2) -1 -> arr
else {
val (lft, rght) = (arr.head, arr.last)
val area = (lft min rght) * (arr.length - 1)
if (lft <= rght) area -> arr.dropWhile(_ <= lft)
else area -> arr.reverse.dropWhile(_ <= rght)
}
}.takeWhile(_._1 >= 0).maxBy(_._1)._1
}
The idea is to iterate lazily and the take (i.e. realize) only those you need.
You'll note that this iterates, and calculates areas, fewer times because it drops values that can't beat the current area calculation.
answered Nov 16 '18 at 20:42
jwvhjwvh
28.6k52142
Here's a way to implement your algorithm without recursion (not that I actually think there's anything inherently wrong with recursion).
def maxArea2(a: Array[Int]): Int = {
Stream.iterate(0 -> a){ case (_, arr) =>
if (arr.length < 2) -1 -> arr
else {
val (lft, rght) = (arr.head, arr.last)
val area = (lft min rght) * (arr.length - 1)
if (lft <= rght) area -> arr.dropWhile(_ <= lft)
else area -> arr.reverse.dropWhile(_ <= rght)
}
}.takeWhile(_._1 >= 0).maxBy(_._1)._1
}
The idea is to iterate lazily and the take (i.e. realize) only those you need.
You'll note that this iterates, and calculates areas, fewer times because it drops values that can't beat the current area calculation.
answered Nov 16 '18 at 20:42
jwvhjwvh
28.6k52142
answered Nov 16 '18 at 20:42
jwvhjwvh
28.6k52142
answered Nov 16 '18 at 20:42
jwvhjwvh
28.6k52142
answered Nov 16 '18 at 20:42
jwvhjwvh
28.6k52142
28.6k52142
Thanks!, so it seems this approach would be more efficient?
– ElBaulP
Nov 17 '18 at 14:36
add a comment |
Thanks!, so it seems this approach would be more efficient?
– ElBaulP
Nov 17 '18 at 14:36
Thanks!, so it seems this approach would be more efficient?
– ElBaulP
Nov 17 '18 at 14:36
Thanks!, so it seems this approach would be more efficient?
– ElBaulP
Nov 17 '18 at 14:36
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53342810%2ffind-maximun-area-on-array%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Re recursion/goto, for those interested, the related paper
– Lasf
Nov 16 '18 at 20:14
@eukaryota Removed
– ElBaulP
Nov 17 '18 at 14:35