title: Count Least Possible Steps to Create zig-zag array
body: <p>Given an array, I need to find the least possible changes you can make to the array to create a zig-zag pattern.</p>
  <p>Edit: What you can change: any individual integer in the array can be changed to any other negative or positive integer. Each change counts as one change.</p>
  <p>I am trying to do this:</p>
  <ol>
  <li>count the number of steps it would take to make an array follow a Higher-Lower-Higher-Lower... pattern</li>
  <li>count the number of steps it would take to make an array follow a Lower-Higher.... pattern</li>
  <li>return whichever value is lower</li>
  </ol>
  <p>This is what I have:</p>
  <pre><code>def minOperations(arr):
      def first(arr): 
          count1 = 0
          i = 1
          k = len(arr)
          while i &lt; k-1:
              if arr[i-1] &lt; arr[i] &gt; arr[i+1] :
                  i += 2
              elif arr[i-1] &gt; arr[i] &gt; arr[i+1]:
                  arr[i] = arr[i-1]+1
                  i += 2
                  count1 += 1
              elif arr[i-1] &lt; arr[i] &lt; arr[i+1]:
                  arr[i] = arr[i+1]+1
                  i+= 2
                  count1 += 1
              elif arr[i-1] == arr[i]:
                  arr[i] = (abs(arr[i-1])+abs(arr[i+1]))
                  count1 += 1
                  i += 2
              elif arr[i-1] &lt; arr[i] == arr[i+1]:
                  arr[i] = arr[i+1]+1
                  count1 += 1
                  i += 2
              else:
                  i += 1
          return count1
      
      def second(arr):
          ij = 1
          k = len(arr)
          count2=0
          while ij &lt; k-1:
              if arr[ij-1] &gt; arr[ij] &lt; arr[ij+1] :
                  ij += 2
              elif arr[ij-1] &gt; arr[ij] &gt; arr[ij+1]:
                  arr[ij] = arr[ij+1]-1
                  ij += 2
                  count2 += 1
              elif arr[ij-1] &lt; arr[ij] &lt; arr[ij+1]:
                  arr[ij] = arr[ij-1]-1
                  ij+= 2
                  count2 += 1
              elif arr[ij-1] == arr[ij]:
                  arr[ij] = -arr[ij-1]
                  count2 += 1
                  ij += 2
              elif arr[ij] == arr[ij+1]:
                  arr[ij] = arr[ij+1]-1 - abs(arr[ij-1])
                  count2 += 1
                  ij += 2
              else:
                  ij += 1
          return count2
          
      count1 = first(arr)
      count2 = second(arr)
      return count1 if count1&lt;count2 else count2  
  </code></pre>
  <p>Edit 2: The input is any integer array; the output is an integer that indicates the least possible number of changes to create a zigzag pattern either starting with arr[0]&gt;arr[1]&lt;arr[2]&gt;arr[3]... or arr[0]&lt;arr[1]&gt;arr[2]...</p>
  <p>If I remove</p>
  <pre><code>def second(arr)...
  </code></pre>
  <p>It works well for the most part.</p>
  <p>With this 1000 line input, I am struggling to get the correct output (below)</p>
  <pre><code>328197
  363438
  472137
  345559
  60946
  627327
  183828
  849130
  242550
  892962
  7187
  281898
  209661
  790519
  550382
  624706
  254124
  782425
  211198
  659851
  10354
  357163
  217450
  883220
  44827
  955766
  169162
  854588
  117042
  903769
  17762
  885946
  135683
  445904
  497484
  958949
  404979
  186542
  10898
  641823
  344338
  880793
  526586
  911492
  700304
  938989
  226824
  165157
  803100
  993861
  166742
  928772
  157133
  867061
  292956
  90243
  149877
  470695
  72677
  977232
  648027
  569858
  22317
  892887
  14025
  171706
  260033
  828342
  559788
  876944
  87869
  794434
  275226
  915727
  50276
  823785
  989018
  425056
  73215
  642967
  473985
  771130
  753696
  233807
  351268
  746285
  451650
  681027
  61847
  803064
  142924
  890204
  168920
  947287
  295166
  291483
  23263
  681024
  776371
  997878
  102663
  321166
  134949
  829965
  648311
  878591
  529136
  745078
  177903
  78275
  832972
  959703
  532512
  463897
  201307
  425243
  21888
  975033
  292061
  194727
  407446
  909738
  124842
  777764
  162651
  662567
  231691
  717646
  55756
  971066
  252498
  238159
  739710
  978460
  183002
  977365
  207875
  648246
  710076
  948142
  215751
  242685
  258102
  864638
  177147
  229747
  939399
  932241
  22872
  794227
  217924
  232337
  129451
  222378
  597788
  914905
  230122
  854759
  134067
  504350
  27561
  904514
  36274
  762897
  393025
  264655
  131081
  987606
  888853
  754043
  977050
  732715
  757720
  741456
  728966
  920744
  798
  543591
  249110
  806599
  308879
  994725
  573471
  967319
  439221
  604181
  58477
  902805
  510995
  506352
  362362
  959919
  565211
  476263
  27576
  885937
  400157
  101338
  262661
  895580
  229121
  777818
  964503
  984581
  491699
  713034
  193745
  905040
  31361
  983969
  317200
  295865
  160783
  987288
  159884
  186978
  41694
  958739
  994182
  922872
  424719
  977047
  109190
  973826
  479498
  817424
  354980
  198544
  61500
  517363
  23037
  620589
  230926
  66926
  207576
  177396
  302743
  845741
  825537
  938814
  583557
  878375
  238637
  603651
  12115
  832149
  847472
  839401
  804
  661265
  290065
  621816
  71446
  737597
  4181
  982173
  75138
  486600
  555688
  681095
  728118
  888748
  46659
  810802
  69
  549599
  104851
  229697
  381540
  712053
  347686
  933548
  247650
  743351
  84302
  997960
  62957
  597689
  488655
  942522
  484294
  534092
  203312
  720374
  483144
  834370
  305673
  718235
  364918
  653087
  229442
  123224
  134495
  891738
  670887
  967626
  89248
  864129
  151126
  938639
  138432
  5214
  66158
  362661
  222853
  700786
  45133
  676405
  803494
  351289
  21810
  927950
  15320
  929592
  5155
  472950
  169497
  894672
  120801
  725758
  619500
  547694
  28524
  948142
  225903
  858028
  28510
  748989
  167273
  590548
  67519
  350189
  55375
  956223
  702790
  563110
  292533
  452575
  67277
  877019
  754434
  835717
  20767
  953471
  173809
  650835
  151891
  521316
  205242
  218007
  56265
  913137
  66061
  821257
  60582
  566025
  179435
  989696
  347024
  270780
  144873
  780658
  92780
  840431
  291735
  156864
  349302
  700372
  130859
  576462
  412629
  928774
  556507
  873185
  411899
  939763
  262434
  385892
  108388
  915159
  106566
  860734
  396517
  799058
  18058
  506397
  623146
  830562
  67608
  984449
  94775
  989789
  884538
  591099
  71226
  856843
  100282
  775910
  11967
  643223
  153892
  815066
  42720
  854598
  15212
  54041
  36957
  848847
  732856
  819383
  135390
  737982
  57296
  893295
  560676
  809539
  791488
  586312
  84313
  582595
  91980
  775586
  48873
  826671
  827479
  998851
  904428
  995151
  143635
  972117
  950058
  964104
  131270
  890428
  290350
  966854
  97623
  917920
  157453
  10120
  361511
  932771
  15813
  907585
  339007
  762581
  102583
  972461
  840323
  692793
  729636
  807253
  856766
  550142
  289765
  622888
  619975
  424141
  977415
  966652
  30657
  541677
  415821
  960728
  47272
  739919
  300762
  913847
  61501
  848489
  80525
  883427
  247481
  979434
  50146
  958739
  247920
  507894
  484169
  289573
  982594
  794655
  100492
  836137
  151021
  994348
  122966
  967989
  182287
  828264
  48141
  230447
  143962
  960671
  573434
  790754
  38658
  496945
  12953
  787685
  256242
  926000
  172657
  933034
  487354
  798104
  453801
  823459
  11234
  991942
  116727
  576391
  461814
  123890
  325432
  610035
  480382
  828031
  4469
  290066
  131284
  973092
  60532
  210258
  358830
  865727
  57944
  986482
  16823
  770264
  74481
  197650
  10793
  642297
  16962
  902237
  777079
  681962
  700512
  783454
  176443
  924479
  349557
  877241
  207654
  902509
  73449
  612458
  29129
  755547
  18077
  918403
  128568
  641007
  182711
  965469
  47265
  41143
  61465
  79311
  135612
  951546
  22735
  868128
  704358
  811349
  39387
  539892
  946874
  743027
  154142
  990373
  332072
  880675
  938760
  407495
  341690
  974812
  278478
  735654
  234691
  986436
  140316
  416537
  36407
  965504
  304827
  937473
  260734
  977852
  152933
  907524
  187616
  888363
  436522
  987305
  656519
  772481
  328055
  653446
  227311
  378351
  394638
  30687
  25283
  934339
  3117
  872381
  166140
  812168
  688435
  964276
  347667
  705230
  115808
  940031
  294903
  980610
  55076
  375923
  80573
  311950
  468136
  758353
  191212
  839169
  245686
  915738
  131293
  903068
  141074
  955285
  388188
  954095
  129075
  128928
  263373
  797046
  266491
  995049
  628273
  960800
  66567
  69127
  61098
  878089
  123
  699668
  984976
  895127
  220031
  939581
  29749
  994388
  1320
  949982
  28634
  849004
  10266
  613541
  196380
  984660
  98345
  997074
  207798
  952922
  189705
  164858
  374786
  876171
  790207
  968442
  266027
  243544
  217943
  690640
  946609
  776698
  881703
  70221
  222314
  964105
  59961
  978357
  48529
  878338
  15179
  990407
  92183
  932184
  787799
  901454
  270989
  728431
  23765
  222811
  616164
  219023
  19955
  769092
  808504
  550899
  722723
  912808
  172846
  771989
  738710
  818958
  650669
  176457
  229587
  292988
  181425
  103561
  337825
  761696
  88039
  917717
  60143
  664772
  99961
  985142
  286124
  784990
  11843
  54164
  218203
  899471
  297103
  767562
  315044
  858645
  205953
  644189
  130421
  739974
  5219
  586177
  5583
  857333
  878900
  913682
  12960
  652965
  613322
  997252
  251004
  220104
  380202
  845684
  334917
  951368
  209577
  823907
  102519
  21845
  173914
  742672
  222100
  507651
  23063
  985880
  83772
  566232
  61129
  170670
  39797
  891075
  3583
  964360
  5224
  927321
  669554
  992526
  273589
  78312
  671954
  915466
  121923
  850013
  3338
  876476
  5212
  495578
  130474
  487426
  271587
  816651
  58460
  278416
  227535
  884303
  228687
  660093
  397348
  851898
  93338
  778385
  310449
  639258
  877448
  366024
  26610
  880237
  21023
  136089
  249222
  428539
  491685
  851212
  80734
  727120
  59089
  808965
  24763
  356163
  399712
  486300
  787365
  814778
  43432
  732872
  323521
  843631
  31254
  653174
  339844
  679982
  184657
  960323
  807314
  395412
  856508
  913017
  224117
  725355
  146413
  722724
  25988
  912918
  146255
  962750
  97375
  760831
  329082
  198664
  62189
  998309
  64327
  912759
  334927
  974018
  972488
  925986
  114922
  826841
  148960
  851782
  724731
  915705
  655480
  662665
  541710
  182442
  329411
  962333
  288501
  585919
  406460
  433782
  317811
  838200
  402317
  975313
  216259
  879319
  115537
  723288
  952426
  820203
  227715
  740605
  379197
  25358
  949486
  84443
  359426
  750785
  806696
  882475
  377821
  204627
  32755
  992234
  9128
  944969
  833
  585486
  964576
  631439
  605105
  748724
  226322
  819242
  601299
  823059
  229323
  946733
  177192
  112452
  8607
  850708
  718531
  213095
  160315
  568756
  712654
  865907
  43581
  867157
  396980
  892108
  380873
  987459
  424395
  732801
  991481
  884131
  317686
  681721
  61692
  807032
  136571
  944546
  945521
  930013
  92924
  9194
  21941
  915733
  127849
  136100
  31967
  987334
  152865
  939505
  33733
  795893
  75096
  994529
  695478
  859934
  277490
  969429
  287283
  928623
  92334
  975776
  190895
  955485
  209296
  633376
  695442
  807863
  29025
  595913
  50719
  926766
  311643
  53989
  608741
  994526
  243690
  930411
  119019
  130867
  47691
  726931
  105419
  915314
  89595
  403712
  449363
  674701
  20005
  461330
  74355
  972027
  130303
  235828
  186451
  63342
  32933
  263523
  819628
  896245
  101501
  647686
  180592
  726535
  </code></pre>
  <p>count1 comes to 112</p>
  <p>The correct output is 106</p>
  <p>I'm thinking I've got the def first(arr) down alright where the only changes are addition. When the changes leading to the most efficient output include subtraction(s) then I'm missing those.</p>
  <p>I have a feeling there is a much simpler solution. I just am not seeing it. How would you approach this problem?</p>
  <p>PS: Thank you for bearing with me on my first stackoverflow post. Doing my best to provide the details to sort this out.</p>