Discussion on Array Manipulation Challenge

Sort by

recency

|

2481 Discussions

|

6 hours ago+ 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;
}

6 days ago+ 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();
    }
}

3 weeks ago+ 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
    }

3 weeks ago+ 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; }

4 weeks ago+ 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.

Sort by

|

2481 Discussions

|

Cookie support is required to access HackerRank