# Make the array non-decreasing with the given operation

Given an array **arr[]** of size **N**, the task is to check if it is possible to make the array non-decreasing by applying the given operation at most once on each array element. In a single operation, one can decrease the element by one i.e. **arr[i] = arr[i] – 1**.**Examples:**

Input:arr[] = {1, 2, 1, 2, 3}Output:Yes

Apply the given operation on the 2^{nd}and the 4^{th}element.

Now, the array becomes {1, 1, 1, 1, 3}Input:arr[] = {1, 3, 1}Output:No

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the

DSA Self Paced Courseat a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.In case you wish to attend

live classeswith experts, please referDSA Live Classes for Working ProfessionalsandCompetitive Programming Live for Students.

**Approach:** Process the elements in increasing order and decrease the current element whenever it can be done without making it less than the previous element. (The first element should thus always be decreased.) If at any point the current element is less than the previous element then no matter what operation is performed, the answer is “No”.

The reason this strategy is optimal is that decreasing a number will make it easier (or at least easy) to deal with the next element in the list, since any value the next element could have taken will still work when the previous number is lower, and in fact decreasing the previous number expands the range of possible values for the next set.

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to make array non-decreasing` `bool` `isPossible(` `int` `a[], ` `int` `n)` `{` ` ` `// Take the first element` ` ` `int` `cur = a[0];` ` ` `// Perform the operation` ` ` `cur--;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = 1; i < n; i++) {` ` ` `// Next element` ` ` `int` `nxt = a[i];` ` ` `// If next element is greater than the` ` ` `// current element then decrease` ` ` `// it to increase the possibilities` ` ` `if` `(nxt > cur)` ` ` `nxt--;` ` ` `// It is not possible to make the` ` ` `// array non-decreasing with` ` ` `// the given operation` ` ` `else` `if` `(nxt < cur)` ` ` `return` `false` `;` ` ` `// Next element is now the current` ` ` `cur = nxt;` ` ` `}` ` ` `// The array can be made non-decreasing` ` ` `// with the given operation` ` ` `return` `true` `;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `a[] = { 1, 2, 1, 2, 3 };` ` ` `int` `n = ` `sizeof` `(a) / ` `sizeof` `(a[0]);` ` ` `if` `(isPossible(a, n))` ` ` `cout << ` `"Yes"` `;` ` ` `else` ` ` `cout << ` `"No"` `;` ` ` `return` `0;` `}` |

## Java

`// Java implementation of the approach` `class` `GFG` `{` `// Function to make array non-decreasing` `static` `boolean` `isPossible(` `int` `a[], ` `int` `n)` `{` ` ` `// Take the first element` ` ` `int` `cur = a[` `0` `];` ` ` `// Perform the operation` ` ` `cur--;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = ` `1` `; i < n; i++)` ` ` `{` ` ` `// Next element` ` ` `int` `nxt = a[i];` ` ` `// If next element is greater than the` ` ` `// current element then decrease` ` ` `// it to increase the possibilities` ` ` `if` `(nxt > cur)` ` ` `nxt--;` ` ` `// It is not possible to make the` ` ` `// array non-decreasing with` ` ` `// the given operation` ` ` `else` `if` `(nxt < cur)` ` ` `return` `false` `;` ` ` `// Next element is now the current` ` ` `cur = nxt;` ` ` `}` ` ` `// The array can be made non-decreasing` ` ` `// with the given operation` ` ` `return` `true` `;` `}` `// Driver code` `public` `static` `void` `main(String []args)` `{` ` ` `int` `a[] = { ` `1` `, ` `2` `, ` `1` `, ` `2` `, ` `3` `};` ` ` `int` `n = a.length;` ` ` `if` `(isPossible(a, n))` ` ` `System.out.printf(` `"Yes"` `);` ` ` `else` ` ` `System.out.printf(` `"No"` `);` `}` `}` `// This code is contributed by 29AjayKumar` |

## Python3

`# Python3 implementation of the approach` `# Function to make array non-decreasing` `def` `isPossible(a, n) :` ` ` `# Take the first element` ` ` `cur ` `=` `a[` `0` `];` ` ` `# Perform the operation` ` ` `cur ` `-` `=` `1` `;` ` ` `# Traverse the array` ` ` `for` `i ` `in` `range` `(` `1` `, n) :` ` ` `# Next element` ` ` `nxt ` `=` `a[i];` ` ` `# If next element is greater than the` ` ` `# current element then decrease` ` ` `# it to increase the possibilities` ` ` `if` `(nxt > cur) :` ` ` `nxt ` `-` `=` `1` `;` ` ` `# It is not possible to make the` ` ` `# array non-decreasing with` ` ` `# the given operation` ` ` `elif` `(nxt < cur) :` ` ` `return` `False` `;` ` ` `# Next element is now the current` ` ` `cur ` `=` `nxt;` ` ` `# The array can be made non-decreasing` ` ` `# with the given operation` ` ` `return` `True` `;` `# Driver code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` `a ` `=` `[ ` `1` `, ` `2` `, ` `1` `, ` `2` `, ` `3` `];` ` ` `n ` `=` `len` `(a);` ` ` `if` `(isPossible(a, n)) :` ` ` `print` `(` `"Yes"` `);` ` ` `else` `:` ` ` `print` `(` `"No"` `);` `# This code is contributed by AnkitRai01` |

## C#

`// C# implementation of the approach` `using` `System;` ` ` `class` `GFG` `{` `// Function to make array non-decreasing` `static` `Boolean isPossible(` `int` `[]a, ` `int` `n)` `{` ` ` `// Take the first element` ` ` `int` `cur = a[0];` ` ` `// Perform the operation` ` ` `cur--;` ` ` `// Traverse the array` ` ` `for` `(` `int` `i = 1; i < n; i++)` ` ` `{` ` ` `// Next element` ` ` `int` `nxt = a[i];` ` ` `// If next element is greater than the` ` ` `// current element then decrease` ` ` `// it to increase the possibilities` ` ` `if` `(nxt > cur)` ` ` `nxt--;` ` ` `// It is not possible to make the` ` ` `// array non-decreasing with` ` ` `// the given operation` ` ` `else` `if` `(nxt < cur)` ` ` `return` `false` `;` ` ` `// Next element is now the current` ` ` `cur = nxt;` ` ` `}` ` ` `// The array can be made non-decreasing` ` ` `// with the given operation` ` ` `return` `true` `;` `}` `// Driver code` `public` `static` `void` `Main(String []args)` `{` ` ` `int` `[]a = { 1, 2, 1, 2, 3 };` ` ` `int` `n = a.Length;` ` ` `if` `(isPossible(a, n))` ` ` `Console.WriteLine(` `"Yes"` `);` ` ` `else` ` ` `Console.WriteLine(` `"No"` `);` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` `// JavaScript implementation of the approach` `// Function to make array non-decreasing` `function` `isPossible(a, n)` `{` ` ` ` ` `// Take the first element` ` ` `var` `cur = a[0];` ` ` `// Perform the operation` ` ` `cur--;` ` ` `// Traverse the array` ` ` `for` `(` `var` `i = 1; i < n; i++)` ` ` `{` ` ` `// Next element` ` ` `var` `nxt = a[i];` ` ` `// If next element is greater than the` ` ` `// current element then decrease` ` ` `// it to increase the possibilities` ` ` `if` `(nxt > cur)` ` ` `nxt--;` ` ` `// It is not possible to make the` ` ` `// array non-decreasing with` ` ` `// the given operation` ` ` `else` `if` `(nxt < cur)` ` ` `return` `false` `;` ` ` `// Next element is now the current` ` ` `cur = nxt;` ` ` `}` ` ` `// The array can be made non-decreasing` ` ` `// with the given operation` ` ` `return` `true` `;` `}` `// Driver Code` `var` `a = [ 1, 2, 1, 2, 3 ];` `var` `n = a.length;` `if` `(isPossible(a, n))` ` ` `document.write(` `"Yes"` `);` `else` ` ` `document.write(` `"No"` `);` `// This code is contributed by Khushboogoyal499` `</script>` |

**Output:**

Yes