{"id":10560,"date":"2022-09-24T03:27:33","date_gmt":"2022-09-23T21:57:33","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/"},"modified":"2022-09-24T03:27:33","modified_gmt":"2022-09-23T21:57:33","slug":"solved-algorithm-for-understanding-behavior-of-arrays-duplicate","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/","title":{"rendered":"[Solved] Algorithm for understanding behavior of arrays [duplicate]"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

Basically it stores deltas rather than the final list; that means each operation only takes 2 reads and writes rather than (b – a + 1). Then the final max<\/code> scan adds the deltas as it goes along, which is still an O(n)<\/code> operation which you would have had to do anyway.<\/p>\n

n, inputs = [int(n) for n in input().split(\" \")]\n<\/code><\/pre>\n
Get the list size (n) and number of operations (m), ie 5<\/code> and 3<\/code><\/p>\n
list = [0]*(n+1)\n<\/code><\/pre>\n
Create an empty 0-filled list. Should be lst = [0] * n<\/code> (do not use list<\/code> as a variable name, it shadows the built-in type) (we do not need an extra end cell, except as a checksum on our algorithm – if it works properly the final checksum should be 0).<\/p>\n
for _ in range(inputs):\n    x, y, incr = [int(n) for n in input().split(\" \")]\n<\/code><\/pre>\n
Get an operation (a, b, k) ie 1<\/code>, 2<\/code>, 100<\/code>.<\/p>\n
    list[x-1] += incr\n<\/code><\/pre>\n
Add delta to the starting cell<\/p>\n
    if((y)<=len(list)): \n        list[y] -= incr\n<\/code><\/pre>\n
Subtract the delta from the ending cell (should be if y < n: lst[y] -= incr<\/code>)<\/p>\n
The algorithm may be easier to understand if you add a print(lst)<\/code> here (after the if<\/code> but inside the for<\/code> loop).<\/p>\n
Now process the deltas to find the maximum item:<\/p>\n
max = x = 0\nfor i in list:\n    x=x+i;\n<\/code><\/pre>\n
x<\/code> is now the value the actual value of the current list cell. Also max<\/code> is a terrible variable name because it shadows the built-in max()<\/code> function.<\/p>\n
    if(max<x):max=x\n<\/code><\/pre>\n
Keep a running max tally<\/p>\n
print(max)\n<\/code><\/pre>\n
Show the result.<\/p>\n<\/p><\/div>\n
<\/div>\n<\/div>\n
            <\/span> <\/p><\/div>\n<\/div>\n
[ad_2]<\/p>\n
solved Algorithm for understanding behavior of arrays [duplicate] <\/p>\n","protected":false},"excerpt":{"rendered":"
[ad_1] Basically it stores deltas rather than the final list; that means each operation only takes 2 reads and writes rather than (b – a + 1). Then the final max scan adds the deltas as it goes along, which is still an O(n) operation which you would have had to do anyway. n, inputs … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[457,325,349],"class_list":["post-10560","post","type-post","status-publish","format-standard","hentry","category-solved","tag-algorithm","tag-performance","tag-python"],"yoast_head":"\n[Solved] Algorithm for understanding behavior of arrays [duplicate] - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] Algorithm for understanding behavior of arrays [duplicate] - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] Basically it stores deltas rather than the final list; that means each operation only takes 2 reads and writes rather than (b – a + 1). Then the final max scan adds the deltas as it goes along, which is still an O(n) operation which you would have had to do anyway. n, inputs ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-09-23T21:57:33+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] Algorithm for understanding behavior of arrays [duplicate]\",\"datePublished\":\"2022-09-23T21:57:33+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/\"},\"wordCount\":202,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"algorithm\",\"performance\",\"python\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/\",\"name\":\"[Solved] Algorithm for understanding behavior of arrays [duplicate] - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-09-23T21:57:33+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] Algorithm for understanding behavior of arrays [duplicate]\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] Algorithm for understanding behavior of arrays [duplicate] - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] Algorithm for understanding behavior of arrays [duplicate] - JassWeb","og_description":"[ad_1] Basically it stores deltas rather than the final list; that means each operation only takes 2 reads and writes rather than (b – a + 1). Then the final max scan adds the deltas as it goes along, which is still an O(n) operation which you would have had to do anyway. n, inputs ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/","og_site_name":"JassWeb","article_published_time":"2022-09-23T21:57:33+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] Algorithm for understanding behavior of arrays [duplicate]","datePublished":"2022-09-23T21:57:33+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/"},"wordCount":202,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["algorithm","performance","python"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/","url":"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/","name":"[Solved] Algorithm for understanding behavior of arrays [duplicate] - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-09-23T21:57:33+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-algorithm-for-understanding-behavior-of-arrays-duplicate\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] Algorithm for understanding behavior of arrays [duplicate]"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/10560","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=10560"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/10560\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=10560"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=10560"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=10560"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}