Array ChallengeHave the function ArrayChallenge(arr) read the array of non-negative integers stored in arr which will represent the heights of bars on a graph (where each bar width is 1), and determine the largest area underneath the entire bar graph. For example: if arr is [2, 1, 3, 4, 1] then this looks like the following bar graph:You can see in the above bar graph that the largest area underneath the graph is covered by the x's. The area of that space is equal to 6 because the entire width is 2 and the maximum height is 3, therefore 2 * 3 = 6. Your program should return 6. The array will always contain at least 1 element.ExamplesInput: {6, 3, 1, 4, 12, 4}Output: 12Input: {5, 6, 7, 4, 1}Output: 16
Question
Array ChallengeHave the function ArrayChallenge(arr) read the array of non-negative integers stored in arr which will represent the heights of bars on a graph (where each bar width is 1), and determine the largest area underneath the entire bar graph. For example: if arr is [2, 1, 3, 4, 1] then this looks like the following bar graph:You can see in the above bar graph that the largest area underneath the graph is covered by the x's. The area of that space is equal to 6 because the entire width is 2 and the maximum height is 3, therefore 2 * 3 = 6. Your program should return 6. The array will always contain at least 1 element.ExamplesInput: {6, 3, 1, 4, 12, 4}Output: 12Input: {5, 6, 7, 4, 1}Output: 16
Solution
This problem can be solved using a stack data structure. Here are the steps:
- Initialize a variable
max_areato 0 and an empty stack. - Iterate over the array from left to right.
- For each bar, if the stack is empty or the current bar is higher than the bar at the top index of the stack, push the current index to the stack.
- If the current bar is lower than the bar at the top index of the stack, then keep removing the top of the stack until we find a bar on stack which is lower than current. Calculate area every time we remove. If the stack is empty, meaning the current bar is the lowest so far, the area is
input[top] * i. If the stack is not empty, the area isinput[top] * (i - stack.peek() - 1). Updatemax_areaif area is more thanmax_area. - After the end of the array, pop all the bars from the stack and calculate area same as step 4.
- Return
max_area.
Here is the Java code for the above steps:
public static int ArrayChallenge(int[] arr) {
Stack<Integer> stack = new Stack<>();
int max_area = 0;
int i = 0;
while (i < arr.length) {
if (stack.empty() || arr[stack.peek()] <= arr[i]) {
stack.push(i++);
} else {
int top = stack.pop();
int area = arr[top] * (stack.empty() ? i : i - stack.peek() - 1);
max_area = Math.max(max_area, area);
}
}
while (!stack.empty()) {
int top = stack.pop();
int area = arr[top] * (stack.empty() ? i : i - stack.peek() - 1);
max_area = Math.max(max_area, area);
}
return max_area;
}
This function takes an array of integers as input and returns the largest area underneath the bar graph. The time complexity is O(n) and the space complexity is O(n) where n is the size of the input array.
Similar Questions
Array ChallengeHave the function ArrayChallenge(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array (excluding the largest number) can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers.ExamplesInput: [5,7,16,1,2]Output: falseInput: [3,5,-1,8,12]Output: true
Array ChallengeHave the function ArrayChallenge(arr) take the array of numbers stored in arr which will contain 5 positive integers, the first two representing a range of numbers (a to b), the next 2 also representing another range of integers (c to d), and a final 5th element (x) which will also be a positive integer, and return the string true if both sets of ranges overlap by at least x numbers. For example: if arr is [4, 10, 2, 6, 3] then your program should return the string true. The first range of numbers are 4, 5, 6, 7, 8, 9, 10 and the second range of numbers are 2, 3, 4, 5, 6. The last element in the array is 3, and there are 3 numbers that overlap between both ranges: 4, 5, and 6. If both ranges do not overlap by at least x numbers, then your program should return the string false.ExamplesInput: {5,11,1,5,1}Output: trueInput: {1,8,2,4,4}Output: false
Given an integer array arr, write a program to find the subarray which has the largest sum and return its sum. If the array is empty, return 0.Sample Input:9-2 -1 -3 4 -1 2 1 -5 4Sample Output: 6Explanation:The subarray is [4, -1, 2, 1] and the sum is 6
Have the function ArrayChallenge(arr) take the array of numbers stored in arr and first determine the largest element in the array, and then determine whether or not you can reach that same element within the array by moving left or right continuously according to whatever integer is in the current spot. If you can reach the same spot within the array, then your program should output the least amount of jumps it took. For example: if the input is [2, 3, 5, 6, 1] you'll start at the spot where 6 is and if you jump 6 spaces to the right while looping around the array you end up at the last element where the 1 is. Then from here you jump 1 space to the left and you're back where you started, so your program should output 2. If it's impossible to end up back at the largest element in the array your program should output -1. The largest element in the array will never equal the number of elements in the array. The largest element will be unique.
Given two arrays (arr1[], arr2[]) of integers, display the largest number in arr1, where that element should not be present in arr2. If the constraint is not satisfied return 0.Variable Constraints:Size of the array <= 5;Array data type = integer.Input:Size of array 1Elements of array 1Size of array 2Elements of array 2Output:Largest element in array 1
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.