Sort by

recency

|

2481 Discussions

|

  • + 0 comments

    My approach in JavaScript :-)

    function arrayManipulation(n, queries) {
        let diff = new Array(n + 1).fill(0);
    
        for (let i = 0; i < queries.length; i++) {
            // destructure the array
            let [a, b, k] = queries[i];
            
            // do the prefix sum
            diff[a - 1] += k;
            diff[b] -= k;    
        }
        
        let sum = 0;
        let max = -Infinity;
            
        for (let j = 0; j < n; j++) {
            sum += diff[j];
            
            if (sum > max) {
                max = sum;
            }
        }
        return max;
    }
    
  • + 0 comments

    Hi Friends,

    7 Tests are failing due to timeout error. Pls Help.

    using System.CodeDom.Compiler;
    using System.Collections.Generic;
    using System.Collections;
    using System.ComponentModel;
    using System.Diagnostics.CodeAnalysis;
    using System.Globalization;
    using System.IO;
    using System.Linq;
    using System.Reflection;
    using System.Runtime.Serialization;
    using System.Text.RegularExpressions;
    using System.Text;
    using System;
    using System.Numerics;
    using System.Collections.ObjectModel;
    
    class Result
    {
        public static long arrayManipulation(int n, ReadOnlySpan<List<int>> span)
        {
            if (!(n >= 3 && n <= Math.Pow(10, 7)))
            {
                return 0;
            }
            var initial = new List<long>();
            for (int i = 0; i < n; i++)
            {
                initial.Add(0);
            }
    
            for (int c = 0; c < span.Length; c++)
            {
                for (int i = 0; i < n; i++)
                {
                    if (i >= span[c][0] - 1 && i < span[c][1])
                    {
                        initial[i] = ((initial[i] + span[c][2]));
                    }
                }
            }
    
            // foreach (var q in queries)
            // {
            //     for (int i = 0; i < n; i++)
            //     {                 
            //         if (i >= q[0] - 1 && i < q[1])
            //         {
            //             initial[i] = ((initial[i] + q[2]));
            //         }                
            //     }
            // }
    
            return initial.Max();
        }
    }
    
    class Solution
    {
        public static void Main(string[] args)
        {
            TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
    
            string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');
    
            int n = Convert.ToInt32(firstMultipleInput[0]);
    
            int m = Convert.ToInt32(firstMultipleInput[1]);
    
            List<List<int>> queries = new List<List<int>>();
    
            for (int i = 0; i < m; i++)
            {
                queries.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(queriesTemp => Convert.ToInt32(queriesTemp)).ToList());
            }
    
            var x = queries.Where(c => c[2] != 0 && c[0] <= n && c[0] >= 1 && c[1] <= n && c[1] >= 1 && c[2] <= Math.Pow(10, 9)).ToList();
            ReadOnlySpan<List<int>> span = new ReadOnlySpan<List<int>>(x.ToArray());
            long result = Result.arrayManipulation(n, span);
    
            textWriter.WriteLine(result);
    
            textWriter.Flush();
            textWriter.Close();
        }
    }
    
  • + 0 comments

    bit ugly but it does the job in scala (60)

    trick is to avoid inner loops for the queries and instead ADD value at the start index and SUBTRACT it at the end index + 1 (due to inclusive bounds)

    also make sure to return long

        def arrayManipulation(n: Int, queries: Array[Array[Int]]): Long = {
          val arr = Array.fill(n)(0)
    
          for (query <- queries) {
            val start = query(0) - 1
            val _end = query(1)
            val value = query(2)
    
            
            arr(start) = arr(start) + value
            if (_end != n) {
              arr(_end) = arr(_end) - value
            }
          }
          var res = 0L
          var run_res = 0L
          for (i <- 0 until n by 1) {
            run_res = run_res + arr(i)
            if (run_res > res){
              res = run_res
            }
          }
    					
    			
          res
        }
    
  • + 0 comments

    Here's my approch

    long arrayManipulation(int n, vector> queries) { vector arr(n,0); long a=0,max=0; long value,start,end;

    for(int i=0; imax)max=arr[j]; } } return max; }

  • + 0 comments

    My Javascript solution:

    function arrayManipulation(n, queries) {
        // creating an array with the values needed to form the result array
        let sumArray = Array(n + 1).fill(0)
        queries.forEach(q => {
            let a = q[0] - 1
            let b = q[1]
            let k = q[2]
            
            sumArray[a] += k
            sumArray[b] -= k
        })
        
        // actually creating the result array
        let currentValue = 0
        sumArray.forEach((s, i) => {
            currentValue += s
            sumArray[i] = currentValue
        })
        
        // extracting the maximum value
        let maxValue = 0
        sumArray.forEach(s => {
            if(s > maxValue) {
                maxValue = s
            }
        })
        
        return maxValue
    }
    

    The key point to understand from this solution is that the goal is to reduce the big O, and the way we do this is by avoiding the most logical way to approach this problem, which could be a nested loop. For example, we could loop through the queries array and then, inside it, loop n times to perform each operation in order to form the final array. But this would result in O(mn) time complexity.

    Now, it's worth noticing that it doesn't really matter how many loops we go through, as long as they're not nested.

    That's why in my solution, I don't iterate the queries array in order to form the final array, but instead, I go through it to form an array that allows me to form the final array by iterating it afterwards.

    Let me give you an example. Let's say that I get this input: n **= 5 **a b k 2 4 2

    Then, my resulting array after iterating the queries array would be: [0, 2, 0, 0, -2, 0] (remember that my array size is n+1 to store the last substraction, but is not relevant)

    That doesn't tell us much at first glance, but if we iterate that array assigning the value of the summatory to each position, the result array would be: [0, 2, 2, 2, 0, 0]

    Here's how: 0 0 + 2 = 2 2 + 0 = 2 2 + 0 = 2 2 + (-2) = 0 0 + 0 = 0 // this last element is just for calculation purposes

    And... That's how we got the resultant array without nested loops!

    Once I have the resultant array I just need to find the Max value of it.

    As you can see I used 3 loops which results in O(a + b + c) but as you know, we dont care about less dominant terms so that can be reduced to O(n).

    Hope this explanation helps to understand the solution.