Create non-decreasing-array.py

kamyu104 · web-flow · commit cabfa87a9171 · 2017-08-28T22:37:22.000+08:00
diff --git a/Python/non-decreasing-array.py b/Python/non-decreasing-array.py
@@ -0,0 +1,42 @@
+# Time:  O(n)
+# Space: O(1)
+
+# Given an array with n integers, your task is to check if
+# it could become non-decreasing by modifying at most 1 element.
+#
+# We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).
+#
+# Example 1:
+# Input: [4,2,3]
+# Output: True
+# Explanation: You could modify the first 
+# 4
+#  to 
+# 1
+#  to get a non-decreasing array.
+# Example 2:
+# Input: [4,2,1]
+# Output: False
+# Explanation: You can't get a non-decreasing array by modify at most one element.
+# Note: The n belongs to [1, 10,000].
+
+class Solution(object):
+    def checkPossibility(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: bool
+        """
+        modified, prev = False, nums[0]
+        for i in xrange(1, len(nums)):
+            if prev > nums[i]:
+                if modified:
+                    return False
+                if i-2 < 0 or nums[i-2] <= nums[i]:
+                    prev = nums[i]    # nums[i-1] = nums[i], prev = nums[i]
+                else:
+                    prev = nums[i-1]  # nums[i] = nums[i-1], prev = nums[i]
+                modified = True
+            else:
+                prev = nums[i]
+        return True
+ 
