Posts

Maximum Absolute Difference

Image
Problem You are given an array of   N   integers,   A1, A2, .... AN .  Return the maximum value of   f(i, j)   for all 1 ≤ i, j ≤ N.   f(i, j)   is defined as   |A[i] - A[j]| + |i - j| , where |x| denotes absolute value of x and i != j.   Problem Constraints 1 <= N <= 100000 -10 9   <= A[i] <= 10 9 Example Input Input 1: A = [1, 3, -1] Input 2: A = [3, 2, 5, 1] Example Output Output 1: 5 Output 2: 4 Explanation A=[1, 3, -1] f(1, 1) = f(2, 2) = f(3, 3) = 0 f(1, 2) = f(2, 1) = |1 - 3| + |1 - 2| = 3 f(1, 3) = f(3, 1) = |1 - (-1)| + |1 - 3| = 4 f(2, 3) = f(3, 2) = |3 - (-1)| + |2 - 3| = 5 So, we return 5. Question Link https://www.interviewbit.com/problems/maximum-absolute-difference/ Solution We have to find the maximum value of the function f(i,j) = |A[i]-A[j]| + |i-j|. Solution 1: Brute Force A simple solution is to apply two loops and calculate the maximum of the the function f. Algorithm: Initialize diff=0, res=0,...
Post a Comment
Read more

Minimum difference pair

Problem Given an unsorted array, find the absolute minimum difference between any pair in given array. Problem Constraints 1 <=   |arr|   <= 100000, 1 <= arr[i] <= 100000 Example Input Input 1: A = [2, 4, 7, 9] Input 2:  A = [1, 3, 10, 5, 2, 17] Example Output Output 1: 2 Output 2: 1 Question Link https://practice.geeksforgeeks.org/problems/minimum-difference-pair/0 Solution We have to find the absolute minimum difference between any pair in given array. Solution 1: Brute Force   A brute force approach is to find the minimum absolute difference from each pair generated from the array. We simply use two loops to find the each pair and then find the minimum among them. Algorithm:  Initialize min = Integer.MAX_VALUE;  Iterate (i) the array from left to right: Iterate the array j=i+1 from left to right: min = Math.min(min,Math.abs(A.get(j)-A.get(i)));  Return min. Here is the solution: public class Solution { public int findMinDifference(A...
Post a Comment
Read more

Beggars Outside Temple

Problem There are   N   ( N > 0 ) beggars sitting in a row outside a temple. Each beggar initially has an empty pot. When the devotees come to the temple, they donate some amount of coins to these beggars. Each devotee gives a fixed amount of coin(according to his faith and ability) to some   K   beggars sitting next to each other. Given the amount donated by each devotee to the beggars ranging from   i   to   j   index, where   1   <=   i   <=   j   <=   N , find out the final amount of money in each beggar's pot at the end of the day, provided they don't fill their pots by any other means. Example Input: N = 5, D = [[1, 2, 10], [2, 3, 20], [2, 5, 25]] Return: [10, 55, 45, 25, 25] Explanation: => First devotee donated 10 coins to beggars ranging from 1 to 2. Final amount in each beggars pot after first devotee: [10, 10, 0, 0, 0] => Second devotee donated 20 coins to beggars ranging from 2 to...
Post a Comment
Read more

Rain Water Trapped

Problem Given an array arr[]  of N non-negative integers representing height of blocks at index i as A i where the width of each block is 1. Compute how much water can be trapped in between blocks after raining. Problem Constraints 1 <=   |arr|   <= 100000 Example Input Input 1: A = [0, 1, 0, 2] Input 2:  A = [1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Example Output Output 1: 1 Output 2: 6  Question Link https://leetcode.com/problems/trapping-rain-water/ https://practice.geeksforgeeks.org/problems/trapping-rain-water/0   Solution We have to calculate the amount of water to be stored in between the blocks. Solution 1: Brute Force In Brute force approach, We do what it says in the question. For each element in the array, we find the maximum amount of water it can trap. we calculate the minimum of the maximum of left side and right side of the element. Algorithm Initialize res = 0 ; Iterate the array from left to right : Initialize left_max = Integer.MIN_VAL...
Post a Comment
Read more